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
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();
}
#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();
}
