Quick Sort algorithm is algo. for sorting given no of data with complexity 'in order of' n2[O(n2)].Here is the complete program Implemented in C language for Microsoft Windows OS.
#include
#include
void sort(int [],int,int); //prototype of sort()
void partarray(int [],int,int,int *); // prototype of partition()
void main()
{
int i,j,a[8]={13,24,324,41,55,46,37,38};
clrscr();
sort(a,0,7);// call to sort function
//0 points to lower bound
// 7 points to upper bound
for(i=0;i<8;i++)
printf("%d\n",a[i]); //printing sorted array
getch();
}
void sort(int a[],int lb,int ub)
{
int j;
if(lb >=ub) // condition for recursion breaking
return;
partarray(a,lb,ub,&j);
sort(a,lb,j-1); //recursive call to sort() function
sort(a,j+1,ub);
}
void partarray(int a[],int lb,int ub,int *j)
{
int b,down,up,t; //if you see,left most end is
// pointed by up pointer and
// vice versa
b=a[lb];
down=ub;
up=lb;
while(down > up)
{
while(a[up] <= b && up < ub)
up++; //updating up pointer
while(a[down] > b && down >= lb)
down--; //uadating down pointer
if(down > up)
{
t=a[down];
a[down]=a[up];
a[up]=t;
}
}
a[lb]=a[down];
a[down]=b;
*j=down;
}
You can also analyze the time taken by sort() function in Linux OS using 'gettimeofday()' function.
Tidak ada komentar:
Posting Komentar