Data Structures with Generic Types in C++/

...

/

Quicksort

Quicksort

Learn about quick-sort and partitioning algorithms.

We'll cover the following...

The quicksort algorithm is another classic divide-and-conquer algorithm. Unlike merge-sort, which does merging after solving the two subproblems, quicksort does all of its work upfront.

Quicksort is simple to describe: pick a random pivot element, x, from a; partition a into the set of elements less than x, the set of elements equal to x, and the set of elements greater than x; and, finally, recursively sort the first and third sets in this partition.

Visual demonstration

An example is shown in figure.

Press + to interact
An example execution of quickSort(a,0,14,c)
An example execution of quickSort(a,0,14,c)

The implementation of the quickSort() method is as follows:

Press + to interact
quickSort(array<T> &a) {

 quickSort(a, 0, a.length);

  quickSort(array<T> &a, int i, int n) {

 if (n <= 1) return;

 T x = a[i + rand()%n];

 int p = i-1, j = i, q = i+n;

 // a[i..p]<x,  a[p+1..q-1]??x, a[q..i+n-1]>x

 while (j < q) {

   int comp = compare(a[j], x);

   if (comp < 0) {       // move to beginning of array

     a.swap(j++, ++p);

   } else if (comp > 0) {

     a.swap(j, --q);  // move to end of array

   } else {

     j++;              // keep in the middle

   }

}

 // a[i..p]<x,  a[p+1..q-1]=x, a[q..i+n-1]>x

 quickSort(a, i, p-i+1);

 quickSort(a, q, n-(q-i));

All of this is done in place so that instead of making copies of subarrays being sorted, the quickSort(a, i, n) method only sorts the subarray a[i],...,a[i+n−1]a[i],...,a[i + n − 1] ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy