What is Quick Sort algorithm? explain with an example [C source code]

QUICK SORT

Quick sort algorithm sorts the array by positioning each element in its proper position and partitioning the array into two sub arrays at the proper position of the moved element. Quick sort also knows as Partition Exchange Sort

Proper position in the array refers to the position of the element in the array when the position of the element in the array is the same as the position of the element in the sorted array containing the same element.

Pivot selection

Let us consider an array arr[n] consisting of n elements. Now consider an element be chosen from any particulate position in the array. This selected element is called pivot and the position is often chosen based on the logic and implementation. These are four possibilities

  1. Pick first element as pivot.
  2. Pick last element as pivot (implemented here)
  3. Pick a random element as pivot.
  4. Pick median as pivot.

Partitioning & placement

Here we have used the last position as pivot. Now we have selected the pivot element so we have to rearrange rest of the array elements in such a way that -

  • All elements placed to the left of pivot are less than or equal to pivot
  • All elements placed to the right of pivot are greater than pivot

Let us take an example:

Let the initial array contains the elements

 (29, 23, 17, 57, 34, 89, 65, 27)

When the last element (27) is placed in its proper position, the array becomes

(23, 17, (27), 57, 34, 89, 65, 29)

Here 27 is in its proper position (i) in the array. The elements to the left of i (23 17 27) is less than or equal to 27 and the elements to the right of i (57, 34, 89, 65, 29) are greater than 27. Since 27 has reached its final position, the array is partitioned at i(position of 27) into two sub arrays

(23, 17) and (57, 34, 89, 65, 29)

Now each sub array has to be sorted individually. This is done by considering each sub array as an array and applying the above stated process to it.

The left sub array has two elements. Considering it as an array, when the last element (17) is placed in its proper position, it becomes:

(17, 23)

The right sub array has five elements. 

(57, 34, 89, 65, (29))
Considering it as an array, when the last element (29) is placed in its proper position, it becomes:

((29), 34, 89, 65, 57)

Thus the array (considering sorted element and both sub arrays) becomes 

17 23 27 ((29) 34 89 65 57)

The sub arrays are further divided into two sub arrays each resulting in

17, 23, 27, (29), (34, 89, 65, 57)

The process is repeated till the array is sorted. Here are the detailed iterations and the sub array division process. 

(23, 17, (27), 57, 34, 89, 65, 29),
Pivot #2 = 27
Quick Sort [0<->1]
(23, 17), 27, 57, 34, 89, 65, 29,
partition pivot (17)
((17), 23), 27, 57, 34, 89, 65, 29,
Pivot #0 = 17
17, 23, 27, (57, 34, 89, 65, 29),
partition pivot (29)
17, 23, 27, ((29), 34, 89, 65, 57),
Pivot #3 = 29
Quick Sort [4<->7]
17, 23, 27, 29, (34, 89, 65, 57),
partition pivot (57)
17, 23, 27, 29, (34, (57), 65, 89),
Pivot #5 = 57
Quick Sort [6<->7]
17, 23, 27, 29, 34, 57, (65, 89),
partition pivot (89)
17, 23, 27, 29, 34, 57, (65, (89)),
Pivot #7 = 89
Quick sorted array
(17, 23, 27, 29, 34, 57, 65, 89),

The final array obtained is a sorted array.

The quicksort algorithm may be best defined by two methods: QuickSort and Partition.

Quick Sort example code

This method is the top level function of this sorting algorithm. It calls partition and the elements are repositioned. Partition splits all elements in two sub groups and array (x[]) are divided into two sub arrays. Again these two sub arrays are passed to QuickSort recursively until the sub groups become single elements.

An algorithm for this method is as follows:

void QuickSort(int arr[], int low, int high)
{
  int pivot;
  if (low < high) {

    /* partitioning array into two groups */
    pivot = Partition(arr, low, high);

    /* Sub array before pivot */
    QuickSort(arr, low, pivot - 1);

    /* Sub array after pivot */
    QuickSort(arr, pivot + 1, high);
  }
}

Partition() code

This method is used to seek the proper position of pivot element in the array. It also repositions the other elements. The element is placed at the proper position and the position is sent back to the quick() method as an argument.

Partition has argument arr or the original array, Low is the lower position and High is higher position of the array. Initially QuickSort will call partition where low will be zero and high is position of last element in the array or same as array count - 1. Let us consider pivot as arr[high]. be the element whose position is to be found. The position of lowermost element (low) and uppermost element (high) are sent to the method. Let us take two local variable i and j. I will be used to calculate the final position of pivot. J will be used to iterate through the array. i and j are initialized with the values of (low -1) and (low) respectively. It will start an iteration where J is incremented by 1 in each iteration. It checks below steps for all the positions till high -1.

  • I is incremented by 1 if arr[j]<= pivot
  • Elements arr[i] and arr[j] exchanges their position if arr[j]<= pivot

These steps are repeated as long as j <= high -1. Now the control comes out of iteration and Pivot is exchanged with arr[i] <> arr[high].

The algorithm can be best explained by the example taken before:

29 23 17 57 34 89 65 27

Now, we will show how the variable i and j changes their values in partition method and how elements are shifted. The following shows the progress of the array elements.

(29, 23, 17, 57, 34, 89, 65, 27),
partition pivot (27)

((29), 23, 17, 57, 34, 89, 65), [27],
I= -1, J = 0, (29 <= 27) = No Swap  
((29), 23, 17, 57, 34, 89, 65), [27],

(29, (23), 17, 57, 34, 89, 65), [27],
I = 0, J = 1, (23 <= 27) Swap 29 <> 23
(23, (29), 17, 57, 34, 89, 65), [27],

(23, 29, (17), 57, 34, 89, 65), [27],
I = 1, J = 2, (17 <= 27) Swap 29 <> 17
(23, 17, (29), 57, 34, 89, 65), [27],

(23, 17, 29, (57), 34, 89, 65), [27],
I = 1, J = 3, (57 <= 27) = No Swap
(23, 17, 29, (57), 34, 89, 65), [27],

(23, 17, 29, 57, (34), 89, 65), [27],
I = 1, J = 4, (34 <= 27) = No Swap
(23, 17, 29, 57, (34), 89, 65), [27],

(23, 17, 29, 57, 34, (89), 65), [27],
I = 1, J = 5, (89 <= 27) = No Swap
(23, 17, 29, 57, 34, (89), 65), [27],

(23, 17, 29, 57, 34, 89, (65)), [27],
I = 1, J = 6, (65 <= 27) = No Swap
(23, 17, 29, 57, 34, 89, (65)), [27],

Now finally pivot 27 has to be exchanged.

(23, 17, (29), 57, 34, 89, 65, [27],
I = 2, J = 7, (29 <> 27)  Swap
(23, 17, (27), 57, 34, 89, 65, 29),

Partition 1#(0 - I), 2#(I + 1 - 7)
Sub Group 1#(0 - 2), Sub Group #2(3 - 7)

Thus the element 27 reaches its proper position at the end of the partition method. Partition method splits the array into two groups.

An algorithm for the method is as follows:

int Partition (int arr[], int low, int high)
{
  int pivot = arr[high]; /* Pivot is highest element */
 
  int i = (low - 1);  /* Index of smaller element */

  /* Iterate through low to pivot - 1 elements */
  for (int j = low; j <= (high - 1); j++) {

    /* If current element can be placed at left */
    if (arr[j] <= pivot) {

      i++;    /* increment index of smaller element */
      Swap (&arr[i], &arr[j]); /* Exchange */
    }
  }
  Swap(&arr[i + 1], &arr[high]); /* Exchange pivot */
  return (i + 1);
}

Quick sort source code

A fully working program using quicksort algorithm is given below. The coding has been done in C compiler. The main function asks for the size of the array and the elements of the array and sorts the array using quicksort algorithm.

/* Quick sort example */
#include <stdio.h>

#define NOPIVOT -1

int elements[] = {29, 23, 17, 57, 34, 89, 65, 27};
const int count = sizeof(elements)/sizeof(elements[0]);

/* Swap two array elements */
void Swap(int * a, int *b)
{
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

/* Print the entire array with sub array marking with () */
/* It also marks pivot or any selected element */
void PrintArray(int arr[], int low, int high, int pivot)
{
  for (int i = 0; i < count; i++) {
    if(i == low) {
      printf("(");
    }
    if (pivot == i) {
      printf("(");
    }

    printf("%d", arr[i]);

    if (i == high) {
      printf(")");
    }
    if (pivot == i) {
      printf(")");
    }
    printf(", ");
  }
  printf("\n");
}

/* Partition (array, low bound, high bound) */
int Partition (int arr[], int low, int high)
{

  int pivot = arr[high];  
 
  int i = (low -1);

  for (int j = low; j <= (high - 1); j++) {

    PrintArray(arr, low, high - 1, j);
    if (arr[j] <= pivot) {
      i++;
      printf("Swap %d <> %d\n", arr[i], arr[j]);
      Swap (&arr[i], &arr[j]);
    }
    PrintArray(arr, low, high -1, j);
  }
  printf("Swap %d <> %d\n", arr[i+1], arr[high]);
  Swap(&arr[i + 1], &arr[high]);
  PrintArray(arr, low, high, i+1);
  return (i + 1);
}

/* Quick sort (array, low bound, high bound) */
void QuickSort(int arr[], int low, int high)
{
  int pivot;
  if (low < high) {

    /* Print additional info (array, pivot etc) */ 
    printf("Quick Sort [%d<->%d]\n", low, high);
    PrintArray(arr, low, high, NOPIVOT);
    printf("partition pivot (%d)\n", arr[high]);

    pivot = Partition(arr, low, high);

    printf("Pivot #%d = %d\n", pivot, arr[pivot]);

    QuickSort(arr, low, pivot - 1);
    QuickSort(arr, pivot + 1, high);
  }
}
int main(int argc, char* argv[])
{
  /* Call Main sorting algo */
  QuickSort(arr, 0, count - 1);

  printf("Quick sorted array\n");
  PrintArray(arr, 0, count, NOPIVOT);
  return 0;
}

Quick sort output

Quick Sort [0<->7]
(29, 23, 17, 57, 34, 89, 65, 27),
partition pivot (27)
(23, 17, (27), 57, 34, 89, 65, 29),
Pivot #2 = 27
Quick Sort [0<->1]
(23, 17), 27, 57, 34, 89, 65, 29,
partition pivot (17)
((17), 23), 27, 57, 34, 89, 65, 29,
Pivot #0 = 17
Quick Sort [3<->7]
17, 23, 27, (57, 34, 89, 65, 29),
partition pivot (29)
17, 23, 27, ((29), 34, 89, 65, 57),
Pivot #3 = 29
Quick Sort [4<->7]
17, 23, 27, 29, (34, 89, 65, 57),
partition pivot (57)
17, 23, 27, 29, (34, (57), 65, 89),
Pivot #5 = 57
Quick Sort [6<->7]
17, 23, 27, 29, 34, 57, (65, 89),
partition pivot (89)
17, 23, 27, 29, 34, 57, (65, (89)),
Pivot #7 = 89
Quick sorted array
(17, 23, 27, 29, 34, 57, 65, 89),

Quick sort pictorial view

Quick sort by picture

Quick sort further reading

QuickSort - GeeksforGeeks

Quicksort - Wikipedia

Data Structures and Algorithms Quick Sort - TutorialsPoint

Quick Sort Tutorials & Notes | Algorithms | HackerEarth

Quick Sort Algorithm | Studytonight

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions