Quick Sort | CrackEase

Quick Sort

Quick sort is a divide-and-conquer sorting algorithm. It picks a pivot element, partitions the array so that elements smaller than the pivot go to its left and greater elements go to its right, then recursively sorts the partitions.

How it works?

Quick sort works in the following way –

Choose a pivot element.
Partition the array: move elements smaller than pivot to the left and greater to the right.
Recursively apply the same process to left and right partitions until each partition has one element.

You choose a new pivot for each partition. Different pivot strategies affect performance (first, last, random, median-of-three, etc.). The examples below use the last element as pivot.

How to choose Pivot?

First element as pivot
Last element as pivot (used in our examples)
Random element as pivot
Median (median-of-three) pivot

Execution of quick sort

Quicksort works recursively. Partitioning places elements smaller than pivot to the left and greater to the right, producing two sub-arrays. Then quicksort is called recursively on both partitions.

Following pseudo-code demonstrates the algorithm:

QuickSort Algorithm

  
quickSort(arr[], low, high)
{
    if (low < high)
    {
        // partition() returns the pivot index after partitioning
        indexPI = partition(arr, low, high);

        quickSort(arr, low, indexPI - 1);  // left partition
        quickSort(arr, indexPI + 1, high); // right partition
    }
}

Partition Algorithm

  
partition (arr[], low, high)
{
    // pivot selected as right-most element
    pivot = arr[high];

    swapIndex = low - 1;  // index of smaller element

    for (j = low; j <= high - 1; j++)
    {
        if (arr[j] <= pivot)   // element should go to left side
        {
            swapIndex = swapIndex + 1;
            swap(arr[swapIndex], arr[j]);
        }
    }
    swap(arr[swapIndex + 1], arr[high]); // place pivot after smaller elements
    return (swapIndex + 1);
}

Quick Sort Algorithm

Quick Sort Partitioning

Code

  
#include <stdio.h>

/* A utility function to swap two elements */
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

/* Partition function:
   elements on the left of returned index are <= pivot,
   elements on the right are > pivot.
   Pivot chosen as last element (array[high]).
*/
int partition (int array[], int low, int high)
{
    int pivot = array[high];     // pivot
    int swapIndex = low - 1;     // index of smaller element

    for (int j = low; j <= high - 1; j++)
    {
        if (array[j] <= pivot)
        {
            swapIndex++;
            swap(&array[swapIndex], &array[j]);
        }
    }
    swap(&array[swapIndex + 1], &array[high]);
    return (swapIndex + 1);
}

/* Recursive quickSort */
void quickSort(int array[], int low, int high)
{
    if (low < high)
    {
        int indexPI = partition(array, low, high);

        quickSort(array, low, indexPI - 1);  // left partition
        quickSort(array, indexPI + 1, high); // right partition
    }
}

/* Function to display the array */
void display(int array[], int size)
{
    for (int i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");
}

/* Main function to run the program */
int main()
{
    int array[] = {70, 90, 10, 30, 50, 20, 60};
    int size = sizeof(array) / sizeof(array[0]);

    printf("Array before Quick Sorting: ");
    display(array, size);

    quickSort(array, 0, size - 1);

    printf("Array after Quick Sorting: ");
    display(array, size);

    return 0;
}

  
#include <iostream>
using namespace std;

// Function to swap two elements
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Partition function
int partition (int array[], int low, int high)
{
    int pivot = array[high];
    int swapIndex = low - 1;

    for (int j = low; j <= high - 1; j++)
    {
        if (array[j] <= pivot)
        {
            swapIndex++;
            swap(&array[swapIndex], &array[j]);
        }
    }
    swap(&array[swapIndex + 1], &array[high]);
    return (swapIndex + 1);
}

// QuickSort recursive
void quickSort(int array[], int low, int high)
{
    if (low < high)
    {
        int indexPI = partition(array, low, high);
        quickSort(array, low, indexPI - 1);
        quickSort(array, indexPI + 1, high);
    }
}

// Display function
void display(int array[], int size)
{
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int main()
{
    int array[] = {70, 90, 10, 30, 50, 20, 60};
    int size = sizeof(array) / sizeof(array[0]);

    cout << "Array before Quick Sorting: ";
    display(array, size);

    quickSort(array, 0, size - 1);

    cout << "Array after Quick Sorting: ";
    display(array, size);

    return 0;
}

  
// Java implementation of Quick Sort
class Main {
    // Utility to swap elements
    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // Partition using last element as pivot
    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int swapIndex = low - 1;

        for (int j = low; j <= high - 1; j++) {
            if (arr[j] <= pivot) {
                swapIndex++;
                swap(arr, swapIndex, j);
            }
        }
        swap(arr, swapIndex + 1, high);
        return swapIndex + 1;
    }

    // Recursive quickSort
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    static void display(int[] arr) {
        for (int v : arr) System.out.print(v + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {70, 90, 10, 30, 50, 20, 60};
        System.out.print("Array before Quick Sorting: ");
        display(a);
        quickSort(a, 0, a.length - 1);
        System.out.print("Array after Quick Sorting: ");
        display(a);
    }
}

	
Array before Quick Sorting: 70 90 10 30 50 20 60 
Array after Quick Sorting: 10 20 30 50 60 70 90

Facts about Quick Sort

Quicksort is typically implemented in-place (O(1) extra space) though recursion uses O(log n) stack on average.
Average (and best) time complexity: O(n log n).
Worst-case time complexity: O(n²) (e.g., already sorted array with bad pivot choice).
Using good pivot selection (randomized or median-of-three) reduces likelihood of worst case.
Quick sort is cache-friendly because of good locality when operating on arrays.

Time Complexity for Quick Sort

Metric	Value
Best / Average	O(n log n)
Worst	O(n²)
Space Complexity (extra)	O(1) (in-place) / recursion stack O(log n) average

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Quick Sort

Quick Sort