by Dinesh Thakur Category: Searching And Sorting

In this sort an element called pivot is identified and that element is fixed in its place by moving all the elements less than that to its left and all the elements greater than that to its right. Since it partitions the element sequence into left, pivot and right it is referred as a sorting by partitioning.

Instead of moving a single element towards its place, a pair element is moved in a single swap. This makes the sorting quick. After the partitioning, each of the sub-lists is sorted, which will cause the entire array to be sorted.

quickSort(int first,int last)

{

if (first < last) /* if the part being sorted isn't empty */

{

mid = quickParition(first,last);

if (mid-1 > first)

quickSort(first,mid-1);

if (mid+1 < last)

quickSort(mid+1,last);

}

return;

}

The hardest part of quick sort is the partitioning of elements. The algorithm looks at the first element of the array (called the "pivot"). It will put all of the elements which are less than the pivot in the lower portion of the array and the elements higher than the pivot in the upper portion of the array. When that is complete, it can put the pivot between those two sections and quick sort will be able to sort the two sections separately.

The details of the partitioning algorithm depend on counters which are moving from the ends of the array toward the center. Each will move until it finds a value which is in the wrong section of the array (larger than the pivot and in the lower portion or less than the pivot and in the upper portion). Those entries will be swapped to put them into their appropriate sections and the counters will continue searching for out of place values. When the two counters cross, partitioning is complete and the pivot can be swapped to its proper place between the two sections.

QuickParition(first, last)

{

mid_val = data[first]; /* This is the pivot value */

i = first+1;

j = last;

while (i<=j)

{

while ((i < last) && (data[i] <= mid_val))

i++;

while ((j >= first) && (data[j] > mid_val))

j--;

if (i < j)

swap(i,j);

else

i++;

}

if (j != first)

swap(j,first);

return j;

}

About Dinesh Thakur

Dinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.

Search Content

Basic Courses

Advance Courses