facebook like button

24 October, 2013

sorting using quicksort method(divide and conqour method ).

THE NEED:
quicksort is the fastest sort in best average case of complexity O(n logn) in worst average case it is O(n2).
the method is to choose pivot, which in my program is the index such that all number in the left of array[pivot],should be less than array[pivot]. And all number in right should be greater than array[pivot].
Rest will be done by recursion.

CODE:
#include<stdio.h>
#define max 10
void quicksort(int a[],int ,int );
int choosepivot(int a[],int ,int );
int main()
{
int a[max],first=0,last,i,n;
printf("enter lenght of array you want to sort\n");
scanf("%d",&last);
printf("enter the array\n");
for(i=0;i<last;i++){
scanf("%d",&a[i]);
}
quicksort(a,first,last-1);
for(i=0;i<last;i++)
{
printf("%d ",a[i]);
}
}
void quicksort(int a[max],int first,int last)
{
int pivot;
if(first<last)
{
pivot=choosepivot(a,first,last);
quicksort(a,first,pivot-1);
quicksort(a,pivot+1,last);
}
}
int choosepivot(int a[max],int first,int last)
{
int j,temp;
int pivot=first;
j=last;
while(j>pivot)
{
if(a[pivot]<a[pivot+1]){
pivot++;
}
else if(a[j]<a[pivot]){
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
}
else
j--;
}
return pivot;
}





APPROACH:
the function quicksort() sorts the array by dividing them on the basis of index(pivot) that's why this is called as divide and conquer approach.
the function choose pivot ,takes the pivot as first element of the array that is being called.And then check  weather the next to it is greater than the number in a[pivot],if not pivot(index) will move to the next number else it will rotate the next number with the last and moves pivot to the next index.
at last the function returns the pivot .