Quick sort is the fastest internal sorting algorithm with the time complexity of O (n log n). It is a highly efficient algorithm.

This algorithm uses the divide and conquer technique. A divide-and-conquer strategy breaks down algorithms into smaller subproblems, solves each subproblem, and then combines the results to solve the original problem.

• Divide: In Divide, select a pivot element. After that, divide the array into two sub-arrays, with each element in the left sub-array being smaller than or equal to the pivot element and each element in the right sub-array being larger.
• Conquer: Sort two subarrays recursively with Quicksort.
• Combine: Combine the sorted arrays.

Quicksort picks one element as the pivot, and then partitions the array around the pivot element.

The quick sort method divides a large array into two arrays, the first containing values that are smaller than the pivot, and the second containing values that are larger than the pivot.

Following that left and right subarrays are also partitioned using the same method. This continues until the sub-array contains a single element.

Selecting a pivot

A good pivot is essential to the fast implementation of quicksort. However, it is common to determine a good pivot.

The pivot can be chosen randomly from the array, i.e. select the random pivot.

The pivot element can either be the rightmost element or the leftmost element of an array.

Choose the median element as the pivot.

Time Complexity

Best Case O(n log n): It occurs when there is no sorting needed, i.e. the array is already sorted.

Average Case O(n log (n)²): The array elements are in a jumbled order that is not properly ascending and descending.

Worst Case O(n²): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

The space complexity of quick sort is O (n log n).

Example

C Program

#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 */  
/* a[] = array to be sorted, start = Starting index, end = Ending index */ 
void quick_sort(int a[], int start, int end) {  
    if (start < end)  {  
        //p is the partitioning index  
        int p = partition(a, start, end); 
        quick_sort(a, start, p - 1);  
        quick_sort(a, p + 1, end);  
    }  
}  
  
/* function to print an array */  
void print(int a[], int n) {
    for (int i = 0; i < n; i++)  
        printf("%d ", a[i]);  
}  

int main() {  
    int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };  
    int n = sizeof(a) / sizeof(a[0]);  
    printf("Before sorting array elements are - n");  
    print(a, n);  
    
    quick_sort(a, 0, n - 1);  
    printf("nAfter sorting array elements are - n");    
    print(a, n);    
    return 0;  
} 

Java Program

public class QuickSort {  
    /* 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.  */  
    static 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) {  
                // increment index of smaller element  
                i++; 
                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 */  
    /* a[] = array to be sorted, start = Starting index, end = Ending index */  
    static void quickSort(int a[], int start, int end) {  
        if (start < end) {  
            // p is partitioning index  
            int p = partition(a, start, end);  
            quickSort(a, start, p - 1);  
            quickSort(a, p + 1, end);  
        }  
    }  
      
    /* function to print an array */  
    static void print(int a[], int n) {  
        for (int i = 0; i < n; i++)  
            System.out.print(a[i] + " ");  
    }  
    
    public static void main(String[] args) {  
        int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };  
        int n = a.length;  
        System.out.println("nBefore sorting array elements are - ");  
        print(a, n);
        
        quickSort(a, 0, n - 1);  
        System.out.println("nAfter sorting array elements are - ");
        print(a, n);  
        System.out.println();  
    }  
}