Quick Sort

Quick sort is widely used sorting algorithm, it is developed by C.A.R.

In quick sort, it first selects one element called a pivot. After that it rearrange the elements in the array in such a way that all the elements less than the pivot element are appearing before the pivot and all the elements greater than the pivot are appear after the pivot. After this partitioning the pivot is in final position.

Quick sort is fastest algorithm and is the best choice. It is faster than other algorithms like bubble sort, selection sort, and insertion sort. But this can be complex on the flip side.

Quick Sort Example

These are the quick sorting technique.

We choose the first element as a pivot. So set loc at 0 index, left at 0 index and right at 5th index.

Now scan from right to left until a[loc] < a[right], then decrease the value of right.

Since a[loc] > a[right], interchange the two values and set loc = right.

Now scan from left to right until a[loc] > a[left], then increment the value of left.

Since a[loc] < a[left], interchange the values and set loc = left.

Since from right to left, since a[loc] < a[right], decrease the value of right.

Start scanning from left to right. Since a[loc] > a[left], increment the value of left.

Since a[loc] > a[right], interchange the two values and set loc = right.

Complexity of Quick sort

Suppose n is the number of elements in an array.

Best Time Complexity - O(n log(n))
Worst Time Complexity - O(n2)

Quick Sort Program in C

#include <stdio.h>
 
void quick_sort (int [], int, int);
 
int main()
{
    int array[50];
    int size, i;
 
    printf("Enter the number of elements: ");
    scanf("%d", &size); 
    printf("Enter %d numbers : ",size);
    for (i = 0; i < size; i++)
    {
        scanf("%d", &array[i]);
    } 
    quick_sort(array, 0, size - 1);
    printf("Quick Sorted List \n");
    for (i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
 
    return 0;
}
void quick_sort(int array[], int low, int high)
{
    int pivot, i, j, temp;
    if (low < high)
    {
        pivot = low;
        i = low;
        j = high;
        while (i < j) 
        {
            while (array[i] <= array[pivot] && i <= high)
            {
                i++;
            }
            while (array[j] > array[pivot] && j >= low)
            {
                j--;
            }
            if (i < j)
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        temp = array[j];
        array[j] = array[pivot];
        array[pivot] = temp;
        quick_sort(array, low, j - 1);
        quick_sort(array, j + 1, high);
    }
}

Output of the above program :

Enter the number of elements: 5
Enter 5 numbers : 34
78
12
66
22
Quick Sorted List 
12 22 34 66 78