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;
}

Double Ended Queue or Deque : Insertion/ Deletion

Hi All,

one more post coming up about the double ended queue which is also known as deque. A deque is a special type of data-structure in which insertion and deletion can be done at both end. So there are 5 operations for deque.

1. Insert element at front end.
2. Insert element at rear end.
3. Delete element from front end.
4. Delete element from rear end.
5. Display the elements of the deque.

So let me introduce the code for each of these function one by one. Here I will be using f for front index and r for rear index.

1. Insert element at front end.

Here there are 3 cases which needs to be taken care of

case 1. When queue is empty, so here is the code :

if(f == 0 && r == -1)

{

Queue[++r] = val; //value which needs to be added.

return;

}




case 2. when queue have element, but some elements from front has been deleted

if(f != 0)

{

Queue[--f] = val;

return;

}




case 3: when queue is full

if(f ==0 && r != -1)

{

printf("No Space left");

return;

}




2. Insert at rear end

Here only 2 cases needs to take care

case 1. if queue is full

if(r == Queue_SIZE - 1)

{

printf("No Space left");

return;

}




case 2. otherwise

else

{

Queue[++r] = val;

}




3. Delete from front end

Here there will be 3 cases.

case 1 : When front index has larger index than rear, it means there is no elements

if(f>r)

{

printf("No element left to delete");

return;

}




case 2. When there is only one element in the queue

if(f==r)

{

printf("deleted element is = %d",Queue[r]);

f = 0;

r =-1;

return;

}

case 3. otherwise

else

{

printf("deleted element is = %d",Queue[f++]);

}

4. Delete from rear end

Here there will be 2 cases.

case 1. when there is no element

if(f>r)

{

printf("No element to delete");

return;

}

case 2. otherwise

else

{

printf("Deleted element is = %d\n",Queue[r--]);

// now only one element was there in queue then adjust rear and front index

if(f>r)

{

f = 0;

r = -1;

}

5. Display the element

int i;

for(i = f; i

{

printf("%d ",Queue[i]);

}

Hope it will help you to understand the complete logic.