Insertion Sort : In non increasing format

Here is the pseudo code for arranging number in non increasing format using Insertion sort. This is one of the exercise of Book Introduction to Algorithms by CLRS.

//N is array's length
for j = N-1 to 1
   key = A[j];
   i = j + 1;
 
   while i<=N && A[i] > key
            A[i-1] = A[i];
            i = i +1;
   A[i-1] = key;

Input : 5 4 3 2 6
Output : 5 4 3 6 2
              5 4 6 3 2
              5 6 4 3 2
              6 5 4 3 2 [Final]

Check if a character link list is palindrome or not.

Hi Folks,

Here is my implementation for checking whether link list is palindrome or not.

#include <iostream>
#include <stack>
#include <cstdlib>

struct node
{
int data;
struct node *next;
};

using namespace std;

struct node *head;

void addNode(int data)
{
struct node *temp;
temp = (struct node *) malloc(sizeof(struct node));
temp -> next = NULL;
temp->data = data;

if(head == NULL)
head = temp;
else
{
struct node *head1;
head1 = head;
while(head1 ->next != NULL)
{
head1 = head1->next;
}
head1->next = temp;
}
}


int main()
{
int N;
cin >> N;

for(int i=0;i<N;i++)
{
int temp;
cin >> temp;
addNode(temp);
}

struct node *slow, *fast;
stack<int> stk;

slow = head;
fast = head;

while(fast->next != NULL)
{
stk.push(slow->data);
slow = slow->next;
fast = fast->next;
if(fast->next != NULL)
fast = fast->next;
}

if(N %2 != 0)
slow = slow->next;
while(!stk.empty())
{

// cout << (stk.top()) <<" " << (slow->data) <<endl;
if(stk.top() == slow->data)
{
slow = slow->next;
stk.pop();
}
else
{
cout <<"No Pallindrome" <<endl;
return false;
}
}

cout <<"Pallindrome" <<endl;//return true;
}

Generate all combination of elements of an array : Power Set Algorithm

#include

#include

#define MAX 100010

using namespace std;

int arr[MAX];

void powerset(int arr[], vector v, int start, int end)

{

if(start > end)

return;

v.push_back(arr[start]);

vector::iterator i;

for(i = v.begin(); i

{

cout << *i;

}

cout << "\n";

powerset(arr,v,start+1,end);

v.pop_back();

powerset(arr,v,start+1,end);

}

int main()

{

int T,N;

cin >> T;

while(T-- > 0)

{

cin >> N;

for(int i=0;i

cin >> arr[i];

vector v;

powerset(arr,v,0,N-1);

}

return 0;

}

Notes on Insertion Sort

Insertion Sort is a way of sorting elements. While using insertion sort, we traverse from right to left element.

Steps :

1. Assume 0th element is already sorted.
2. Starting i from first element till last :
              -  In a loop(j ), check if the previous element is greater than the comparing element( for example for first time, we will be comparing 1st element to 0th element.)
              - If previous element is greater than comparing element, we will replace the j+1th element with j.[Remember before doing this keep array[i] stored in some variable, as it will be compared to all elements].
              - when loops finished, just replace the last index element with array[i] stored value.


Code :

for(i =1; i{
        int val = arr[i];
        int j = i-1;

        while( j >=0 && A[j] > val)
         {
              A[j+1] = A[j];
              j--;
         }
     
         A[j] = val;
}

Create a structure which can contain any type of data

Generally whenever we create a structure, we define that what kind of data it will be storing. But think it this way, what if you don't know what kind of data structure it can use in future, to avoid that situation. Here is the way :

#include
#include
struct node
{
void *ptr;
struct node *link;
};
int main(void) {
// your code goes here
struct node *head,*temp;
float var = 10.5f;
head = (struct node *)malloc(sizeof(struct node));
*(int *)(head->ptr) =10;
head->link = NULL;

temp = (struct node *)malloc(sizeof(struct node));
*(float *)(temp->ptr) = var;
temp->link = NULL;

head->link = temp;

printf("Value = %d",*(int *)(head->ptr));
printf("Value = %f",*(float *)(temp->ptr));
return 0;
}

Hope it helps you in your next interview :)

Find Next Permutation of given string

Hi Guys,

Here is  the code to find the next permutation of given string. I used the algorithm mentioned by Career Cup and this is solution to IARCS.

So Here is the solution

#include

void nextPermutation(char a[], int size);

 

main()

{

    int Size;

    int length;

    char size[5];

    char string[2000];//here just assuming that there can be 1000 digit number and there will be space in between 2 numbers

    int i=0;

    int j=0;

    int k =0;

    int temp = 0;

    char tempstring[1000];

    //printf("Enter the size of array\n");

    fgets(size,5,stdin);

    //printf("entered string is = %s\n",size);

    Size = size[2] - '0';

    length = size[0] - '0';

    //printf("String length = %d and Size = %d\n",length,Size);

    for(i=0;i < Size; i++)

    {

        fgets(string,2000,stdin);

        j = k = 0;

        while(j<2000 amp="" code="" j="" string="">'\0')

        {

            if(string[j] != 32)

            {

                tempstring[k] = string[j];

                tempstring[++k] = '\0';

            }

            ++j;

        }

        //printf("So the number is = %s and the k = %d\n",tempstring,--k);

        nextPermutation(tempstring,--k);

    }

     

}

 

void nextPermutation(char arr[], int length)

{

    int i=0;

    int temp = 0;

    int pos, maxpos;

    pos = maxpos = -1;

    for(i=0; i

    {

        if(arr[i] < arr[i+1])

        {

            pos = i;

        }

    }

     

    if(pos == -1)

    {

        printf("No next Permutation exist\n");

        return;

    }

     

    for(i=pos+1;i < length;i++)

    {

        if(arr[pos] < arr[i])

            maxpos = i;

    }

    //printf("pos = %d and maxpos = %d and length = %d\n",pos,maxpos,length);

    //swap

    temp = arr[pos];

    arr[pos] = arr[maxpos];

    arr[maxpos] = temp;

     

    for(i=pos+1;i

    {

        temp = arr[i];

        arr[i] = arr[i+1];

        arr[i+1] = temp;

    }

     

    printf("So the next string is \n");

     

    for(i=0;i

        printf("%d ",arr[i]-'0');

    printf("\n");

}