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

- Link: https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/
- Published: 2018-11-10T21:43:39+05:30
- Author: Ashishkumar Vishwakarma

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

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

### Programming for Quick Sort.

### Source Code

    ```c
    #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 1Sorted array:1 2 3 4 5 6 7 8 9
> 10

---

### Programming for Merge Sort.

### Source Code.

    ```c
    #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:233454121Sorted array is :1 12 23 
> 34 54

---

### Source Code.

### Programming for Heap Sort.

    ```c
    #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:1234652356Array after sorting:12 23 34 
> 56 65

Also View:[ – Write a program to create a registration form using AWT](https://technotaught.com/registration-form/).

Also View- [Write a java program to create a window using swing.](https://technotaught.com/22-write-a-java-program-to-create-a-window-using-swing/)

### Share this:

 * [  X ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=twitter)
 * [  Facebook ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=facebook)
 * [More](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/#)

 * [  WhatsApp ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=jetpack-whatsapp)
 * [  LinkedIn ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=linkedin)
 * [  Email ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?subject=%5BShared%20Post%5D%208%3A%20Implementation%20of%20Quick%20Sort%7C%20Merge%20Sort%7C%20Heap%20Sort%20Algorithm.&body=https%3A%2F%2Ftechnotaught.com%2F8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm%2F&share=email)
 * [  Reddit ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=reddit)
 * [  Tumblr ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=tumblr)
 * [  Pinterest ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=pinterest)
 * [  Telegram ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/?share=telegram)
 * [  Print ](https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/#print?share=print)

### _Related_

## Comments

### By: Grace J

- Link: https://technotaught.com/8-implementation-of-quick-sort-merge-sort-heap-sort-algorithm/#comment-127
- Published: 2020-04-22T05:13:21+05:30

Your method of explaining the whole thing in this post is, in fact, pleasant, every
one be capable of effortlessly be aware of it, Thanks a lot.