# 8: Implementation of Quick Sort| Merge Sort| Heap Sort Algorithm.

## 8: Implementation of Quick Sort| Merge Sort| Heap Sort Algorithm.

Q. Sorting Techniques?
ANS.: Quick Sort: Partitioning the array to be sorted and each partition is, in turn, sorted recursively.
Merge Sort: Uses Divide & conquer mechanism, divide the elements & then sort and merge.
Heap Sort: Uses max, min-heap and its operation up adjust, down adjust, del max to sort.

### Source Code

``````#include<stdio.h>
#define SIZE 10

int a[SIZE];

//quick sort
void quick(int low, int high)
{
int i=low;
int j=high;
int temp;
int pivot=a[i];

if(i<j)
{
do
{
while(a[i]<=pivot)//create left sublist such that all eles will be <= pivot
i++;
while(a[j]>pivot)//create right sublist such that all eles will be >pivot
j--;

if(i<=j)//swap so that atleast one ele will be on perfect position
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<=j);

temp=a[low];
a[low]=a[j];
a[j]=temp;

quick(low,j-1);//perform quick sort on left list
quick(j+1,high);//perform quick sort on right list
}
else
return;
}

int main()
{
int i;
//input reverse order array
for(i=0;i<SIZE;i++)
a[i]=SIZE-i;

//print reverse ordered array
printf("Quick sort\nWorst case array:");
for(i=0;i<SIZE;i++)
printf("%d ",a[i]);
printf("\n");

quick(0,SIZE-1);
//print sorted array
printf("Sorted array:");
for(i=0;i<SIZE;i++)
printf("%d ",a[i]);
return 0;
}``````

### Output.

Quick sort
Worst case array:10 9 8 7 6 5 4 3 2 1
Sorted array:1 2 3 4 5 6 7 8 9 10

### Source Code.

``````#include<stdio.h>

void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);

int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:\n");

for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}

void mergesort(int a[],int i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid);        //left recursion
mergesort(a,mid+1,j);    //right recursion
merge(a,i,mid,mid+1,j);    //merging of two sorted sub-arrays
}
}

void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50];    //array used for merging
int i,j,k;
i=i1;    //beginning of the first list
j=i2;    //beginning of the second list
k=0;
while(i<=j1 && j<=j2)    //while elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1)    //copy remaining elements of the first list
temp[k++]=a[i++];
while(j<=j2)    //copy remaining elements of the second list
temp[k++]=a[j++];
//Transfer elements from temp[] back to a[]
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}``````

### Output.

Enter no of elements:5
Enter array elements:
23
34
54
12
1
Sorted array is :1 12 23 34 54

### Programming for Heap Sort.

``````#include<stdio.h>

void create(int []);
int main()
{
int heap[30],n,i,last,temp;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("\nEnter elements:");
for(i=1;i<=n;i++)
scanf("%d",&heap[i]);
//create a heap
heap[0]=n;
create(heap);
//sorting
while(heap[0] > 1)
{
//swap heap[1] and heap[last]
last=heap[0];
temp=heap[1];
heap[1]=heap[last];
heap[last]=temp;
heap[0]--;
}

//print sorted data
printf("\nArray after sorting:\n");
for(i=1;i<=n;i++)
printf("%d ",heap[i]);
}

void create(int heap[])
{
int i,n;
n=heap[0]; //no. of elements
for(i=n/2;i>=1;i--)
}

{
int j,temp,n,flag=1;
n=heap[0];

while(2*i<=n && flag==1)
{
j=2*i;    //j points to left child
if(j+1<=n && heap[j+1] > heap[j])
j=j+1;
if(heap[i] > heap[j])
flag=0;
else
{
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
i=j;
}
}
}``````

### Output.

Enter no. of elements:5
Enter elements:12
34
65
23
56
Array after sorting:
12 23 34 56 65