Quick Sort

Quick Sort is a Divide and Conquer sorting algorithm. It picks an element as pivot element and partitions the given array around the picked pivot such that pivot element comes at its proper sorted position and the elements smaller than pivot element are on its left hand side and the elements larger than pivot element are on its right hand side. Now it recursively sorts the left sub-array and right sub-array of pivot element in the same manner till no further partitioning can be done.

There are many different versions of Quick Sort that pick pivot in different ways, like:

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

The key process in Quick Sort is partitioning. The target of partitions is that given an array and an element x of array as pivot, put x at its correct position (as that in sorted array) and put all elements smaller than x before x and all elements greater than x after x in the array. All this should be done in linear time.

Time complexity: O(n log n) in average case, O(n²) in worst case (Here worst case is when array is sorted or reversely sorted.)
Space complexity: O(log n) in average case, up to O(n) in worst case (This extra space may come from the call stack.)

Although the worst case time complexity of Quick Sort is O(n²) which is more than many other sorting algorithms like Merge Sort and Heap Sort, Quick Sort is faster in practice because its inner loop can be efficiently implemented on most architectures, and in most real-world data. The algorithm can be modified to make it much more efficient. For example, Randomized Quick Sort shows O(n log n) complexity even for worst case, as it picks pivot randomly.

Quick Sort can be implemented in different ways by changing the choice of pivot, so that the worst case rarely occurs for a given type of data. However, Merge Sort is generally considered better when data is huge and stored in external storage.

Below is one of the many ways to implement Quick Sort:

#include <stdio.h>

void swap(int *x, int *y)
{
    int temp = *x;
    *x       = *y;
    *y       = temp;
}

void quickSort(int *A, int Left, int Right)
{
    int i, pos;
    if(Left < Right)
    {
        pos = Left;
        for(i = Left+1; i <= Right; i++)
            if(A[i] < A[Left])
                swap(&A[++pos], &A[i]);   // When order is mismatched, increment pos and swap A[pos] with A[i]

        swap(&A[Left], &A[pos]);   // By now, pos is at proper position for A[Left]. Actually Left acts as pivot element here! Now swap A[Left] with A[pos]

        quickSort(A, Left, pos-1);     // Sort left sub-list
        quickSort(A, pos+1, Right);    // Sort right sub-list
    }
}

int main()
{
    int i, size;
    printf("\n\nEnter size of array: ");
    scanf("%d", &size);
    int A[size];

    printf("\n\nEnter %d elements: \n", size);
    for(i = 0; i < size; i++)
        scanf("%d", &A[i]);
 
    quickSort(A, 0, size-1);

    printf("\n\nQuick sorted: ");
    for(i = 0; i < size; i++)
        printf("%d ", A[i]);
 
    return 0;
}