Data Structures And Algorithms

Implementation of Quick Sort

2007-06-21T15:01:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

int partition(int a[],int p,int q)
{
   int up,down,temp;
   up=p+1;down=q;
   do
   {
   while(a[down]>a[p] &&amp; down>p)
       down-=1;
   while(a[up]<a[p])
       up+=1;
   if(up<down)
   {
       temp=a[up];
       a[up]=a[down];
       a[down]=temp;
   }
   }while(up<down);
   temp=a[down];
   a[down]=a[p];
   a[p]=temp;
   return down;
}      
     
void quick_sort(int a[],int p,int q)
{
   int r;
   if(p>=q)
   return;
   r=partition(a,p,q);
   quick_sort(a,p,r-1);
   quick_sort(a,r+1,q);
}

int main(int argc,char *argv[])
{
   int size,*ar,i;  
   printf("\nEnter the no of elements");
   scanf("%d",&size);
   ar=(int *)malloc(size*sizeof(int));
   printf("\nEnter the elements\n");
   for(i=0;i<size;i++)
       scanf("%d",&ar[i]);
   quick_sort(ar,0,size-1);
   printf("\nThe Sorted List is :\n");
   for(i=0;i<size;i++)
   printf("%d ",ar[i]);
   printf("\n");
   return 0;
}

Merge Sort Explained

2007-06-20T23:52:00.000+05:30

Merge sort or Mergesort is an O(n log n) sorting algorithm. It is easy to implement merge sort such that it is stable, meaning it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It is a comparison sort. The algorithm was invented by John von Neumann in 1945.

Merge sort recursively divides the array of elements into smaller subarrays and sort them and then merge these to form a complete sorted array.

Conceptually, merge sort works as follows:

Divide the unsorted list into two sublists of about half the size
Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
Merge the two sorted sublists back into one sorted list.

Description of the Implementation of Merge Sort:
The program contains 2 important functions.

merge() - This function takes as argument the bounds of parts of array to be merged. These two parts are contiguous and hence only 3 bounds are required. These parts are copied in separate arrays and then actual merging takes place. There are two pointers to the beginning of these arrays. The first elements are compared and smaller one copied to the original array and its pointer incremented. This process continues till one of the arrays exhausts. After this the remaining array is just copied. Thus the two arrays are merged and the result is a sorted array part.
merge_sort() - This function breaks the array into two nearly equal parts and calls merge_sort for these parts. Then it calls the merge() function to merge these parts.

Example:
let the array be 80 32 56 37 69 76.
this is partitioned into 2 parts as
80 32 56 | 37 69 76

now 80 32 56 is partitioned into 2 parts as
80 | 32 56

since 80 is single element list, it is trivially sorted.

now 32 56 is partitioned into 2 parts as
32 | 56

Again these are trivially sorted.

Now merge 32 | 56 results in 32 56

And merge 80 | 32 56 results in 32 56 80

Now 37 69 76 is partitioned into 2 parts as
37 | 69 76

since 37 is single element list, it is trivially sorted.

now 69 76 is partitioned into 2 parts as
69 | 76

Again these are trivially sorted.

Now merge 69 | 76 results in 69 76

And merge 37 | 69 76 results in 37 69 76

At last merge 32 56 80 | 37 69 76 results in sorted array
32 37 56 69 76 80

Implementation of Merge Sort

2007-06-18T19:27:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

void merge(int a[], int p, int q, int r)
{
    int i=0,j=0,k=0,len1,len2;
    len1 = q-p+1;
    len2 = r-q;
    int *a1 = (int *)malloc(len1*sizeof(int));
    int *a2 = (int *)malloc(len2*sizeof(int));
    for(i=p;i<=q;i++)
    a1[j++]=a[i];
    j=0;
    for(i=q+1;i<=r;i++)
    a2[j++]=a[i];
    i=0;j=0,k=p;
    while(i<len1 && j<len2)
    {
    if(a1[i]<a2[j])
        a[k++]=a1[i++];
    else
        a[k++]=a2[j++];
    }
    if(i<len1)
    {
    for(;i<len1;i++)
         a[k++]=a1[i];
    }
    else for(;j<len2;j++)
         a[k++]=a2[j];
}

void merge_sort(int a[], int p, int r)
{
    int q;
    q = (p+r)/2;
    if(!(q-p<=0))
    {
    merge_sort(a,p,q);
    }
    if(!(r-q<=1))
    {
    merge_sort(a,q+1,r);
    }
    merge(a,p,q,r);
       
}


int main(int argc,char *argv[])
{
    int size,*ar,i;   
    printf("\nEnter the no of elements");
    scanf("%d",&size);
    ar=(int *)malloc(size*sizeof(int));
    printf("\nEnter the elements\n");
    for(i=0;i<size;i++)
        scanf("%d",&ar[i]);
    merge_sort(ar,0,size-1);
    printf("\nThe Sorted List is :\n");
    for(i=0;i<size;i++)
        printf("%d ",ar[i]);
    printf("\n");
    return 0;
}

Heap Sort Explained

2007-06-18T02:15:00.000+05:30

Heap Sort is another optimal comparison sort as its time complexity is O(nlgn) in both average and worst cases. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime. Heapsort is an in-place algorithm and is not a stable sort.
The main idea behind heapsort is to construct a heap out of the list of elements to be sorted. From this heap the maximum element (in case of max-heap) or the minimum element (in case of min-heap) can be repeatedly taken out with ease to give the sorted list of elements.

Description of the Implementation Of Heap Sort:
The code uses max-heap for sorting an array. It starts with the macro definitions of left and right children of a node i. The rest of the code consists of 3 functions :

1) max_heapify() : It takes as input the index of node i in an array a whose size is also passed. the node i has the property that both its left and right subtrees are max-heaps. But the tree rooted at node i may not be so. This function makes this tree a max-heap. It traverses the tree starting from node i to the leaves. Every time it compares the node with its left and right children and the maximum of all of them takes the position of the node.

2) build_max-heap() : It is the function for the initial formation of the heap when the sorting starts. It calls max-heapify() function for all non-leaf nodes. This is so because the leaf nodes are trivially max-heaps of size 1. When this function returns, the array becomes a max-heap.

3) heap_sort() : This function is the main heapsort function. It starts by calling the build_max_heap() function on the array. After this function, the max element of the heap is replaced by the last element in the heap and its size is reduced by 1. Then max_heapify() is called from the root of heap. This is continued till the heap contains no more elements.

For example, take the max-heap as
87 34 67 20 18 56 40

Now 87 will be replaced by 40
40 34 67 20 18 56 | 87
after max_heapify()
67 34 56 20 18 40 | 87

Now 67 will be replaced by 40
40 34 56 20 18 | 67 87
after max_heapify()
56 34 40 20 18 | 67 87

Now 56 will be replaced by 18
18 34 40 20 | 56 67 87
after max_heapify()
40 34 18 20 | 56 67 87

Now 40 will be replaced by 20
20 34 18 | 40 56 67 87
after max_heapify()
34 20 18 | 40 56 67 87

Now 34 will be replaced by 18
18 20 | 34 40 56 67 87
after max_heapify()
20 18 | 34 40 56 67 87

Now 20 will be replaced by 18
18 | 20 34 40 56 67 87
after max_heapify()
18 | 20 34 40 56 67 87

Thus the sorted list is 18 20 34 40 56 67 87

Implementation Of Heap Sort

2007-06-13T12:09:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

#define left(i) 2*i+1
#define right(i) 2*i+2

void max_heapify(int a[],int i,int size)
{
    int l,r,largest,temp;
    l=left(i);
    r=right(i);
    if(l<=size-1 && a[l]>a[i])
        largest = l;
    else largest = i;
    if(r<=size-1 && a[r]>a[largest])
        largest = r;
    if(largest != i)
    {
        temp = a[i];
        a[i]=a[largest];
        a[largest]=temp;
        max_heapify(a,largest,size);
    }
}

void build_max_heap(int a[],int size)
{
    int i;
    for(i=size/2 - 1 ;i>=0;i--)
        max_heapify(a,i,size);
}

void heap_sort(int a[],int size)
{
    int i,temp;
    build_max_heap(a,size);
    for(i=size-1;i>0;i--)
    {
        temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        size=size - 1;
        max_heapify(a,0,size);
    }
}

int main(int argc,char *argv[])
{
    int size,*ar,i;   
    printf("\nEnter the no of elements");
    scanf("%d",&size);
    ar=(int *)malloc(size*sizeof(int));
    printf("\nEnter the elements\n");
    for(i=0;i<size;i++)
        scanf("%d",&ar[i]);
    heap_sort(ar,size);
    printf("\nThe Sorted List is :\n");
    for(i=0;i<size;i++)
        printf("%d ",ar[i]);
    printf("\n");
    return 0;
}

Shell Sort Explained

2007-06-13T00:13:00.000+05:30

Shell Sort works on the principle that removes large amount of disorders quickly. It differs from other sorting algorithms as in early stages far-apart elements are compared rather than adjacent ones. This gap is gradually reduced to one and it becomes an adjacent interchange method.

(Image Source: The Art of Computer Programming, vol. 3, D.E. Knuth)

The running time of this algorithm is O(n^2) which is quite inefficient. But the constant factor is much better than insertion or bubble sort.

Description of Implementation Of Shell Sort :
The main() function starts by asking the no of elements and then allocates an array of required size. Then the array is filled up and the shell sort function is called. This function does the actual sorting. After that, the sorted array is printed.

The shell_sort() function starts sorting the array. The outermost for loop takes control of the "gap" between compared elements. In the beginning the gap is half the size of array i.e. elements of one half are compared to corresponding elements in the second half. This gap is gradually reduced to 1. The middle for loop steps along element. The innermost for loop compares elements separated by "gap" and reverses that are out of order.
Since the gap is eventually reduced to 1, all the elements are eventually ordered correctly.

Implementation Of Shell Sort

2007-06-11T21:44:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

void shell_sort(int a[],int size)
{
 int i,j,temp,gap;
 for(gap=size/2;gap>0;gap/=2)
 {
  for(i=gap;i<size;i++)
  {
   for(j=i-gap;j>=0 && a[j]>a[j+gap];j-=gap)
   {
    temp=a[j];
    a[j]=a[j+gap];
    a[j+gap]=temp;
   }
  }
 } 
}

int main(int argc,char *argv[])
{
 int size,*ar,i; 
 printf("\nEnter the no of elements");
 scanf("%d",&size);
 ar=(int *)malloc(size*sizeof(int));
 printf("\nEnter the elements\n");
 for(i=0;i<size;i++)
  scanf("%d",&ar[i]);
 shell_sort(ar,size);
 printf("\nThe Sorted List is :\n");
 for(i=0;i<size;i++)
  printf("%d ",ar[i]);
 printf("\n");
 return 0;
}

Implementation Of Insertion Sort

2007-06-11T19:37:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

void insertion_sort(int a[],int size)
{
 int i,j,temp,small;
 for(i=1;i<size;i++)
 {
  for(j=i;j>0;j--)
  {
   if(a[j]<a[j-1])
   {
    temp=a[j];
    a[j]=a[j-1];
    a[j-1]=temp;
   }
   else
    break;
  }
 } 
}

int main(int argc,char *argv[])
{
 int size,*ar,i; 
 printf("\nEnter the no of elements");
 scanf("%d",&size);
 ar=(int *)malloc(size*sizeof(int));
 printf("\nEnter the elements\n");
 for(i=0;i<size;i++)
  scanf("%d",&ar[i]);
 insertion_sort(ar,size);
 printf("\nThe Sorted List is :\n");
 for(i=0;i<size;i++)
  printf("%d ",ar[i]);
 printf("\n");
 return 0;
}

Implementation Of Selection Sort

2007-06-11T19:19:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

void selection_sort(int a[],int size)
{
 int i,j,temp,small;
 for(i=0;i<size-1;i++)
 {
  small=i;
  for(j=i;j<size;j++)
  {
   if(a[j]<a[small])
    small=j;
  }
  temp=a[i];
  a[i]=a[small];
  a[small]=temp;
 } 
}

int main(int argc,char *argv[])
{
 int size,*ar,i; 
 printf("\nEnter the no of elements");
 scanf("%d",&size);
 ar=(int *)malloc(size*sizeof(int));
 printf("\nEnter the elements\n");
 for(i=0;i<size;i++)
  scanf("%d",&ar[i]);
 selection_sort(ar,size);
 printf("\nThe Sorted List is :\n");
 for(i=0;i<size;i++)
  printf("%d ",ar[i]);
 printf("\n");
 return 0;
}

Implementation Of Bubble Sort

2007-06-11T14:25:00.000+05:30

#include<stdio.h>
#include<stdlib.h>

void bubble_sort(int a[],int size)
{
int i,j,temp;
for(i=0;i<size-1;i++)
{
for(j=0;j<(size-1-i);j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

int main(int argc,char *argv[])
{
int size,*ar,i;
printf("\nEnter the no of elements");
scanf("%d",&size);
ar=(int *)malloc(size*sizeof(int));
printf("\nEnter the elements\n");
for(i=0;i<size;i++)
scanf("%d",&ar[i]);
bubble_sort(ar,size);
printf("\nThe Sorted List is :\n");
for(i=0;i<size;i++)
printf("%d ",ar[i]);
printf("\n");
return 0;
}

Implementation Of Single Linked List

2007-06-11T02:01:00.000+05:30

//Implementation of Single Linked List in C
#include<stdio.h>
#include<stdlib.h>

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

void insert(struct node *ptr, int val)
{
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = val;
new_node->next = ptr->next;
ptr->next=new_node;
}

void delete(struct node *ptr)
{
struct node *p = ptr->next;
ptr->next = p->next;
free(p);
}

void display(struct node *head)
{
head=head->next;
while(head!=NULL)
{
printf("%d -> ",head->data);
head = head->next;
}
printf("NULL");
}

int main(int argc,char *argv[])
{
struct node p,*ptr,*save;
int choice=1,value,pos;

p.next=NULL;

while(choice!=5)
{
printf("\nMENU\n");
printf("1.Insert to Head\n");
printf("2.Insert in the Middle\n");
printf("3.Delete\n");
printf("4.Display\n");
printf("5.Quit\n");
scanf("%d",&choice);
switch(choice)
{
case 1 : printf("\nEnter a number ");
scanf("%d",&value);
insert(&p,value);
break;
case 2 : printf("\nEnter a number ");
scanf("%d",&value);
printf("\nEnter the number after which to be inserted ");
scanf("%d",&pos);
ptr=p.next;
while(ptr!=NULL)
{
if(ptr->data == pos)
{
insert(ptr,value);
break;
}
ptr=ptr->next;
}
break;
case 3 : printf("\nEnter the number to be deleted ");
scanf("%d",&pos);
ptr=p.next;
save=&p;
while(ptr!=NULL)
{
if(ptr->data == pos)
{
delete(save);
break;
}
save=ptr;
ptr=ptr->next;
}
break;
case 4 : display(&p);
break;
}
}
return 0;
}