Quick Sort

It is an efficient sorting algorithm, when implemented well it can be about two or three times faster than merge sort and heap sort.

It is a divide and conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub arrays according to whether they are less than or greater than the pivot.

There are many different versions of quick sort that pick pivot element in different ways.

a)Pick first element as pivot.

b)Pick last element as pivot.

c)Pick random element as pivot.

d)Pick median element as pivot.

---

Animation of quick sort:

---

Pseudo Code for quick_Sort function:

/* low is Starting index,  high is Ending index */
quick_Sort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quick_Sort(arr, low, pi - 1);  // Before pi
        quick_Sort(arr, pi + 1, high); // After pi
    }
}

Pseudo Code for partition():

/* This function makes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
partition (arr[], low, high)
{
    pivot = arr[high]; 
 
    i = (low - 1)  //index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

---

Example of partition:

arr[] = {1, 8, 3, 9, 4, 5, 7} Indexes: 0 1 2 3 4 5 6 low = 0, high = 6, pivot = arr[h] = 7 Initialize index of smaller element, i = -1 Traverse elements from j = low to high-1 j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j]) i = 0 arr[] = {1, 8, 3, 9, 4, 5, 7} // No change as i and j // are same j = 1 : Since arr[j] > pivot, do nothing // No change in i and arr[] j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j]) i = 1 arr[] = {1, 3, 8, 9, 4, 5, 7} // We swap 8 and 3 j = 3 : Since arr[j] > pivot, do nothing // No change in i and arr[] j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j]) i = 2 arr[] = {1, 3, 4, 9, 8, 5, 7} // 8 and 4 Swapped j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] i = 3 arr[] = {1, 3, 4, 5, 8, 9, 7} // 9 and 5 Swapped We come out of loop because j is now equal to high-1. Finally now pivot is at correct position by swapping arr[i+1] and arr[high] (or pivot) arr[] = {1, 3, 4, 5, 7, 9, 8} // 8 and 7 Swapped Now 7 is at its correct place. All elements smaller than 7 are before it and all elements greater than 7 are after it.

---

Implementation using C:

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

void swap(int *a, int *b)
{
    //swap function used for swapping values using 3rd variable t
    int temp = *a;
    *a = *b;
    *b = temp;
}

/*We have taken last function as pivot element,
places the pivot element at its correct position
and places all smaller elements at its left and greater to its right
*/
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low-1);
    int j;
    for(j = low;j <= high-1; j++)
    {
        if(arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return (i+1);
}

void quick_Sort(int arr[],int low, int high)
{
    if(low<high)
    {
        int pi = partition(arr,low,high);

        quick_Sort(arr,low,pi-1);
        quick_Sort(arr,pi+1,high);
    }
}

void printArray(int arr[], int size)
{
    int i;
    for(i=0; i<size;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
int main()
{
    int arr[]={10, 9, 8, 7, 6, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quick_Sort(arr,0,n-1);
    printf("Sorted array is : \n");
    printArray(arr, n);
    return 0;
}

Output:
Sorted array is:
5 6 7 8 9 10

---

Miscellaneous:

Is Quick Sort stable? The default implementation is not stable. However any sorting algorithm can be made stable by considering indexes as comparison parameter. Is Quick Sort In-place? As per the broad definition of in-place algorithm it qualifies as an in-place sorting algorithm as it uses extra space only for storing recursive function calls but not for manipulating the input.