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)
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;
}
Comments :
Post a Comment