QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

• Always pick the first element as a pivot.
• Always pick the last element as a pivot.
• Pick a random element as a pivot.
• Pick median as the pivot.

It is an approach where :

1. An array is divided into sub-arrays by selecting a pivot element (element selected from the array).
   While dividing the array, the pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot.
2. The left and right sub-arrays are also divided using the same approach. This process continues until each subarray contains a single element.
3. At this point, elements are already sorted. Finally, elements are combined to form a sorted array.

Working :

1. Select the pivot element :
   There are different variations of quicksort where the pivot element is selected from different positions. Here, we will be selecting the rightmost element of the array as the pivot element.
2. Rearrange the array :
   Now the elements of the array are rearranged so that elements that are smaller than the pivot are put on the left and the elements greater than the pivot are put on the right.

   Here's how we rearrange the array:
   

   1. A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index.
   2. If the element is greater than the pivot element, a second pointer is set for that element.
   3. Now, pivot is compared with other elements. If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.
   4. Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another smaller element.
   5. The process goes on until the second last element is reached.
   6. Finally, the pivot element is swapped with the second pointer.

3. Divide Sub-arrays :

   Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is repeated.
   The sub-arrays are divided until each subarray is formed of a single element. At this point, the array is already sorted.

Algorithm

Quicksort Algorithm :

        QUICKSORT (array A, start, end)     
        {  
        1 if (start < end)     
        2 {  
        3 p = partition(A, start, end)  
        4 QUICKSORT (A, start, p - 1)    
        5 QUICKSORT (A, p + 1, end)    
        6 }   
        }              

Partition Algorithm :

        PARTITION (array A, start, end)     
        {  
        1 pivot ? A[end]     
        2 i ? start-1     
        3 for j ? start to end -1 {  
        4 do if (A[j] < pivot) {    
        5 then i ? i + 1     
        6 swap A[i] with A[j]   
        7  }}   
        8 swap A[i+1] with A[end]     
        9 return i+1  
        }        

Program using C

//QUICK SORT #include <stdio.h> /* function that consider last element as pivot, place the pivot at its exact position, and place smaller elements to left of pivot and greater elements to right of pivot. */ int partition (int a[], int start, int end) { int pivot = a[end]; // pivot element int i = (start - 1); for (int j = start; j <= end - 1; j++) { // If current element is smaller than the pivot if (a[j] < pivot) { i++; // increment index of smaller element int t = a[i]; a[i] = a[j]; a[j] = t; } } int t = a[i+1]; a[i+1] = a[end]; a[end] = t; return (i + 1); } /* function to implement quick sort */ void quick(int a[], int start, int end) /* a[] = array to be sorted, start = Starting index, end = Ending index */ { if (start < end) { int p = partition(a, start, end); //p is the partitioning index quick(a, start, p - 1); quick(a, p + 1, end); } } /* function to print an array */ void printArr(int a[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", a[i]); } int main() { int a[] = { 24, 9, 29, 14, 19, 27 }; int n = sizeof(a) / sizeof(a[0]); printf("Before sorting array elements are - \n"); printArr(a, n); quick(a, 0, n - 1); printf("\nAfter sorting array elements are - \n"); printArr(a, n); return 0; }