All rights are reserved by Niteesh Kumar.. Theme images by Storman. Powered by Blogger.

Followers

Total Pageviews

Blog Archive

Follow by Email

Translate

Wednesday, 28 December 2016

Program to implement Quick Sort

OBJECTIVE-Write a C program to implement Quick Sort and also plot time complexity.
 

ALGORITHM-
-select a pivot either from
    1-first element
    2-middle element
    3-last element
and with ech iteration arrange the element such that towards left of it lies all element smaller than pivot element and in it's right all element grater than the pivot then repeat the process
quicksort(arr,low,p-1)
quicksort(arr,p+1,high)



#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void quicksort(int *arr,int low,int high)
{
    int n,pivot,i=low,j=high;
    if(low<high)
    {
            pivot=low;
            while(i<j)
            {
                while(arr[i]<=arr[pivot] && i<high)
                i++;
                while(arr[j]>arr[pivot])
                j--;
                if(i<j)
                {
                    n=arr[i];
                    arr[i]=arr[j];
                    arr[j]=n;
                }
            }
        n=arr[pivot];
        arr[pivot]=arr[j];
        arr[j]=n;
        quicksort(arr,low,j-1);
        quicksort(arr,j+1,high);
    }
}
int main()
{
    clock_t start,end,total;
    int n;
    int arr[10005];
    start=clock();
    for(n=0;n<10000;n++)
    scanf("%d",&arr[n]);
    quicksort(arr,0,9999);
    for(n=0;n<10000;n++)
    printf("%d\t",arr[n]);
    printf("\n");
    end=clock();
    printf("time=%lf\n",(double)(end-start)/CLOCKS_PER_SEC);
return 0;
}

0 on: "Program to implement Quick Sort"