Translate

Monday, 10 March 2014

Bubble Sort, Selection Sort, Insertion Sort, Merge Sort,Heap Sort,Quick sort, Shell Sort - C PROGRAMS

Note: All the programs given below have been successfully compiled and executed.To use it in your Program 
          1.Copy the program in Notepad
          2.Save it in tc/bin folder as Sort.C
          3.Execute and view your Output


 Bubble Sort:

Shifts Heavy elements down with Each Pass:-

#include <stdio.h>
#include <conio.h>

void bubble (int x[], int n)
{int i, j, temp;
 for(i = 1; i < n; i++)
    for(j = 0; j < n-i; j++)
       if(x[j+1]<x[j])
 {temp = x[j+1];
  x[j+1] = x[j];
  x[j] = temp;
 }
 return;
}
void main()
{int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
bubble(a, 10);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}


Modified Bubble Sort:

More Effective as it breaks if Array is Sorted:-


#include <stdio.h>
#include <conio.h>

void modi_bubble (int x[], int n)
{
 int i, j, temp, swap = 1;
 for (i=1; swap; i++)
     {swap = 0;
      for(j=0; j<n-i; j++)
if(x[j+1]<x[j])
  {temp = x[j+1];
   x[j+1] = x[j];
   x[j] = temp;
   swap = 1;
  }
      }
return;
}
void main()
{
int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
modi_bubble(a, 10);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}

Selection Sort:

Selects new minimum from Remaining Array(Unsorted)

#include <stdio.h>
#include <conio.h>

void selection (int x[], int n)
{
 int i, j, pos, min;
 for(i = 0; i < n-1; i++)
    {min = x[i];
     pos = i;
     for (j = i+1; j < n; j++)
if(x[j] < min)
  { min = x[j];
    pos = j;
  }
     x[pos] = x[i];
     x[i] = min;
    }
 return;
}

void main()
{
int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
selection (a, 10);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}


Insertion Sort:

Inserts the next element in Sorted Fashion

 #include <stdio.h>
#include <conio.h>

void insertion (int x[], int n)
{ int i, j, no;
  for (i = 0; i < n - 1; i++)
      { no = x[i+1];
for( j = i; j >= 0; j--)
  if( no < x[j])
    x[j+1] = x[j];
  else break;
x[j+1] = no;
      }
  return;
}

void main()
{
int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
insertion(a, 10);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}


Merge Sort:

#include <stdio.h>
#include <conio.h>

void mergesort(int x[], int lb, int ub)
{ void merge(int [], int, int, int);
  int mid;
  if(lb < ub)
    {mid = (lb + ub) / 2;
     mergesort(x, lb, mid);
     mergesort(x, mid+1, ub);
     merge(x, lb, mid, ub);
    }
}
void merge(int x[], int lb1, int ub1, int ub2)
{
int temp[10], i = lb1, j = ub1 + 1, k = 0;
while(i <= ub1 && j <= ub2)
     if(x[i] < x[j])
       temp[k++] = x[i++];
     else temp[k++] = x[j++];
while(i <= ub1)
     temp[k++] = x[i++];
while(j <= ub2)
     temp[k++] = x[j++];
for (i = lb1, j = 0; i <= ub2; i++, j++)
x[i] = temp[j];
}

void main()
{
int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
mergesort(a, 0, 9);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}


Heap Sort:

#include <stdio.h>
#include <conio.h>

void swap(int *a, int *b)
{ int temp = *a;
      *a = *b;
      *b = temp;
}

void heapup(int x[], int root, int bottom)
{
int parent, temp;
if(bottom > root)
  { parent = (bottom -1) / 2;
    if (x[parent] < x[bottom])
       {swap(&x[parent], &x[bottom]);
heapup(x, root, parent);
       }
  }
}

void heapdown(int x[], int root, int bottom)
{int lchild = 2*root+1, rchild = 2*root+2, maxchild, temp;
  if (lchild <= bottom)
     {if(lchild == bottom)
 maxchild = lchild;
      else if(x[lchild] > x[rchild])
   maxchild = lchild;
else maxchild = rchild;
      if(x[root] < x[maxchild])
{swap(&x[root], &x[maxchild]);
heapdown(x, maxchild, bottom);
}
     }
}

void heapsort(int x[], int n)
{int i, temp;
for(i = 0; i < n-1; i++)
   heapup(x, 0, i+1);
for(i = n-1; i > 0; i--)
   {swap(&x[0], &x[i]);
    heapdown(x, 0, i-1);
   }
}

void main()
{
int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
heapsort(a, 10);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}


Quicksort:

#include <stdio.h>
#include <conio.h>
int partition (int x[], int lb, int ub)
{int pos = lb, i, temp;
 for (i = lb+1; i <= ub; i++)
    if (x[i] < x[lb])
       {pos++;
temp = x[pos];
x[pos] = x[i];
x[i] = temp;
       }
 temp = x[pos];
 x[pos] = x[lb];
 x[lb] = temp;
 return pos;
}
void quicksort(int x[], int lb, int ub)
{int partition(int x[], int, int);
 int p;
 if(lb < ub)
   {p = partition(x, lb, ub);
    quicksort(x, lb, p-1);
    quicksort(x, p+1, ub);
   }
}

Shell Sort:


#include <stdio.h>
#include <conio.h>

void shell (int x[], int n)
{int i, j, k, no, inc;
 for (inc = n/2; inc >=1; inc/=2)
     for (k = 0; k < inc ; k++)
{/* This is insertion sort */
 for (i = k; i < n-inc; i+=inc)
     { no = x[i+inc];
for (j = i; j >= k; j-=inc)
   if(no > x[j])
      break;
   else x[j+inc] = x[j];
x[j+inc] = no;
     }
 /* insertion sort ends */
 }
 return;
}
void main()
{
int i;
int a[] = {40, 70, 20, 90, 100, 80, 10, 60, 30, 50};
clrscr();
shell(a, 10);
for(i = 0; i < 10; i++)
    printf("%d ", a[i]);
printf("\n");
getch();
}