QUICK SORT

Quick sort is based on the divide-and-conquer approach based on the idea of choosing one element as a pivot element and partitioning the array around it such that : Left side of pivot contains all the elements that are less than the pivot element and Right side contains all the elements greater than the pivot element.

There are many different ways to choose the pivot value, we will simply use the first item in the list. At the point where rightmark becomes less than leftmark, we stop. The position of rightmark is now the split point. The pivot value can be exchanged with the contents of the split point and the pivot value is now in place. In addition, all the items to the left of the split point are less than the pivot value, and all the items to the right of the split point are greater than the pivot value. The list can now be divided at the split point and the quick sort can be invoked recursively on the two halves.

Quick Sort Programming in C
 #include //Global function declaration void QuickSort(int a[],int start,int end); int Partition(int a[],int start,int end); void main() { int array[]={54, 25, 92, 18, 84, 45, 56, 20}; int i; QuickSort(array,0,7); for(i=0; i<8; i++) { printf("\t%d",array[i]); } } //QuickSort( ) function void QuickSort(int a[],int start,int end) { int pivot_pos; if(start < end) { pivot_pos = Partition(a, start, end ); //Sorts the left side of pivot. QuickSort(a, start, pivot_pos-1); //Sorts the right side of pivot. QuickSort( a, pivot_pos+1, end); } } //Partition( ) function int Partition(int a[],int start,int end) { int pivot, leftmark, rightmark, temp; leftmark = start+1; rightmark = end; //Make the first element as pivot element. pivot = a[start]; while(leftmark < rightmark) { while(leftmark <= rightmark && a[leftmark] <= pivot) leftmark = leftmark + 1; while(leftmark <= rightmark && a[rightmark] >= pivot) rightmark = rightmark - 1; if (leftmark <= rightmark) { temp = a[leftmark]; a[leftmark] = a[rightmark]; a[rightmark] = temp; } } //Put the pivot element in its proper place. temp = a[start]; a[start] = a[rightmark]; a[rightmark] = temp; //Return the position of the pivot return rightmark; }

Alternet Partition( ) function
 int Partition(int a[],int start,int end) { int i, j, pivot, temp; i=start+1; //Make the first element as pivot element. pivot = a[start]; for(int j=start+1 ; j <= end ; j++) { /* Rearrange the array by putting elements which are less than pivot on one side and which are greater than on other. */ if ( a[j] < pivot) { temp=a[i]; a[i]=a[j]; a[j]=temp; i=i+1; } } //Put the pivot element in its proper place. temp=a[start]; a[start]=a[i-1]; a[i-1]=temp; //Return the position of the pivot return (i-1); }

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.

MORE TOPIC

WHAT WE DO

 Follow Us 