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.
No comments:
Post a Comment