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.

Programming for Quick 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

Programming for Merge Sort.

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

Source Code.

Programming for Heap Sort.

#include<stdio.h>
 
void create(int []);
void down_adjust(int [],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]--;
        down_adjust(heap,1);
    }
 
    //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--)
        down_adjust(heap,i);
}
 
void down_adjust(int heap[],int 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

Also View: – Write a program to create a registration form using AWT.

Also View- Write a java program to create a window using swing.