C Program To Perform Quick Sort

Quick sort is an internal sorting technique which is also called partition-exchange sort.  It is a divide and conquer algorithm.  It works by partitioning the array into two sub arrays, such that the elements in the left side should be lesser than the pivot and the elements in the right side are greater than pivot.  Then recursively sort both the arrays(conquer).  Below are the steps involved in sorting:

1. Select a key value as pivot from the given array.
2. Rearrange the key values in the array so that all the elements in the left side of pivot are lesser than the pivot and the elements in the right side are greater than the value of pivot.
3. Recursively sort both the sub-arrays

pivot    i                                    j
17       12      6     19    23    8    5 10
a[j] is not greater than pivot (10 < 17).  So, process left sub-array.
a[i] < pivot(12 < 17).  So, increment i.

pivot          i                              j
17      12      6 19 23 8 5 10

pivot                  i                      j
17 12 6 19 23 8 5 10
a[i] is not less than pivot and a[j] is not greater than pivot(i < j).  So, swap a[i] and a[j].

pivot                  i                       j
17      12     6       10    23     8     5 19
Start processing right sub-array.  Increment j (a[j] > pivot)

pivot                  i j
17 12 6 10 23 8 5 19
a[j]  is not greater than pivot.  So, start processing left sub-array.

pivot                         i j
17 12 6 10 23 8 5 19
a[i] is not lesser than pivot and i < j.  Swap a[i] and a[j]

pivot                         i j
17 12 6 10 5 8    23 19
Start processing right sub array once again.

pivot                         i j
17 12 6 10      5 8 23 19
a[j] is not greater than pivot(process left sub-array)

pivot   i,j
17 12 6 10 5 8 23 19

pivot   j       i
17  12 6 10 5 8 23 19
i > j
So, swap pivot element and a[j]

8 12 6 10 5 17 23 19

Left sub-array(elements on the left side of pivot): 8  12  6  10  5
Right sub-array: 23  19

Recursively process left sub-array and right sub-array.
8 12 6 10 5     17     23     19

pivot   i                      j             pivot   i,j
8       12        6      10     5    17     23    19

pivot   i                       j
8        5         6 10 12   17     19     23
In left sub-array, i is lesser than j.  So, swap a[i] and a[j].
In right sub-array, i is not lesser than j.  So, swap a[j] and pivot.  Elements in right sub-array are sorted now.

pivot   i  j
8        5        6 10 12      17        19       23

pivot    i        j
8         5        6 10 12      17        19       23

pivot i,j
8         5        6 10 12      17        19       23

pivot j        i
8 5 6 10 12      17        19       23
i >j.. So, pivot and a[j]

6 5      8 10 12      17        19       23
Left sub-array to the key element 8  : 6     5
Right sub-array to the key element 8 : 10   12

6 5      8 10 12      17        19       23

pivot    i,j             pivot   i,j
6           5     8 10       12      17        19       23
Swap pivot and a[j] of left sub-array.
Increment j of right sub-array

                         pivot, j    i
5        6        8        10       12       17        19       23
i is not lesser than j.  So, swap a[j] and pivot

5        6        8        10       12       17        19       23

See Also:

C Program To Perform Insertion Sort

C Program To Perform Shell Sort

C Program To Perform Bubble Sort

C Program To Perform Quick Sort

C Program To Perform Radix Sort

C Program To Perform Selection Sort

C Program To Perform Heap Sort

C Program To Perform Merge Sort

C Program To Perform External Sorting

C Program To Perform Sorting Using Binary Search Tree

Example Program For Quick Sort:

---

  #include <stdio.h>
  #include <stdlib.h>

  int quickSort(int *data, int left, int right) {
        int pivot = left;
        int i = left +1, j = right, temp;
        if (left < right) {
        while (1) {
                while (data[j] > data[pivot])
                        j--;
                while (data[i] <= data[pivot])
                        i++;
                if (i < j) {
                        temp = data[i];
                        data[i] = data[j];
                        data[j] = temp;
                } else
                        break;
        }
        temp = data[pivot];
        data[pivot] = data[j];
        data[j] = temp;
        quickSort(data, left, j-1);
        quickSort(data, j+1, right);
        }
        return 0;
  }

  int main() {

        int i, j, num, *data;

        printf("Enter ur number of entries:");

        scanf("%d", &num);

        data = (int *)malloc(sizeof (int) * num);

        for (i = 0; i < num; i++) {

                scanf("%d", &data[i]);

        }

        quickSort(data, 0, num-1);

        printf("After sorting:\n");

        for (i = 0; i < num; i++)

                printf("%3d", data[i]);

        printf("\n");

        return;

  }

  Output: (C Program To Perform Quick Sort)

  jp@jp-VirtualBox:$ ./a.out
  Enter ur number of entries:8
  17 12 6 19 23 8 5 10
  After sorting:
  5  6  8 10 12 17 19 23