Quick Sort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

1. Choose a pivot element from the array.
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
3. Recursively apply the quick sort algorithm to the two sub-arrays.
4. Combine the sorted sub-arrays to get the final sorted array.

   Quick-Sort(A, P, R)
1. if (P > R)
2.     Q <--- Partition(A, P, R)
3.     Quick-Sort(A, P, Q - 1)
4.     Quick-Sort(A, Q + 1, R)
5. Stop

   Partition(A, P, R)
1. x <--- A[ R ]
2. i <--- P - 1
3. for j <--- P to R - 1
4.     if A[ j ] <= x
5.         i <--- i + 1
6.         exchange( A[ i ] <---> A [ j ] )
7. exchange( A[ i + 1 ] <---> A [ R ] )
8. return ( i + 1 )

#include <stdio.h>
#include <limits.h>

int array[10];

void input_array(int[], int);
void print_array(int[], int);
void quick_sort(int[], int, int);
int partition(int[], int, int);

void main()
{
    input_array(array, 5);
    quick_sort(array, 1, 5);
    print_array(array, 5);
}

void input_array(int A[], int N)
{
    int i;

    printf("Enter the values for sorting :-\n");
    for (i = 1; i <= N; i++)
    {
        printf("Value %d :", i);
        scanf("%d", &A[i]);
    }
}

void print_array(int A[], int N)
{
    int i;

    printf("\nSorted array is : {");
    for (i = 1; i <= N; i++)
    {
        if (i != N)
            printf("%d, ", A[i]);
        else
            printf("%d}", A[i]);
    }
}

void quick_sort(int A[], int P, int R)
{
    int Q;

    if (P < R)
    {
        Q = partition(A, P, R);
        quick_sort(A, P, Q - 1);
        quick_sort(A, Q + 1, R);
    }
}

int partition(int A[], int P, int R)
{
    int x, i, j, temp;

    x = A[ R ];
    i = P - 1;

    for (j = P; j <= R - 1; j++)
    {
        if (A[ j ] <= x)
        {
            i++;
            temp = A[ i ];
            A[ i ] = A[ j ];
            A[ j ] = temp;
        }
    }

    temp = A[ i + 1 ];
    A[ i + 1 ] = A[ R ];
    A[ R ] = temp;
    
    return ( i + 1 );
}

1. Choose Pivot:

   • Select a pivot element from the array (commonly the last element).

2. Partition:

   • Rearrange the array elements such that elements smaller than the pivot are on the left, and elements greater are on the right.
   • The pivot is now in its sorted position.

3. Recursion:

   • Recursively apply the quick sort algorithm to the sub-array on the left of the pivot and the sub-array on the right.

4. Combine:

   • The sorted sub-arrays are combined with the pivot to produce the final sorted array.

Consider an example:

Original List: 5, 3, 8, 4, 2

Pass 1:

• Choose 2 as the pivot, partition into [2] and [5, 3, 8, 4]
• Recursively apply quick sort to [5, 3, 8, 4]

Pass 2:

• Choose 4 as the pivot, partition into [3] and [4, 5, 8]
• Recursively apply quick sort to [3], [5, 8]

Pass 3:

• Choose 3 as the pivot, partition into [ ] and [3]
• Combine sorted sub-arrays [ ] + [3] + [4, 5, 8]

Final Result:

• [2, 3, 4, 5, 8]

• Worst case: O(n^2)
• Average and best case: O(n log n)

• O(log n) - Quick Sort is an in-place sorting algorithm.

• Quick Sort is not stable, meaning the relative order of equal elements may change after sorting.