Quick Sort

Quick Sort is an efficient sorting algorithm widely used in practical scenarios due to its low average time complexity. It employs the divide-and-conquer approach by selecting a "pivot" element to partition the array into two parts and recursively sorting the subarrays. This article explains the principle and steps of Quick Sort in detail, providing code examples in C and Go to help beginners get started quickly.

Principle

The core idea of Quick Sort is:

Select a pivot element (usually the first, last, or a random element of the array).
Partition the array into two parts: elements smaller than the pivot are placed on the left, and elements greater than the pivot are placed on the right (the partitioning process).
Recursively apply Quick Sort to the left and right subarrays.
When the subarray has a length of 1 or 0, the recursion stops.

Its average time complexity is O(n log n), where n is the length of the array, with a worst-case complexity of O(n²) (e.g., if the array is already sorted or reverse-sorted). Despite the worst-case scenario, Quick Sort is generally faster in practice than Insertion Sort or Bubble Sort.

Steps

Assuming we want to sort an integer array in ascending order, here are the detailed steps for Quick Sort:

Choose a Pivot: Select an element from the array as the pivot, for example, the last element.
Partition: Rearrange the array so that elements smaller than the pivot are on its left, and elements greater than the pivot are on its right, with the pivot element in the middle.
Recursion: Recursively call Quick Sort on the subarrays to the left and right of the pivot.
Termination: When a subarray has a length of less than or equal to 1, the sorting is complete.

Implementation

Here is the C implementation of Quick Sort, with detailed comments to aid understanding.

main.c
#include <stdio.h>

// Swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function: selects the last element as the pivot
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Select the last element as the pivot
    int i = low - 1;      // Boundary of the region with elements smaller than the pivot
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++; // Expand the region of smaller elements
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]); // Place the pivot in its correct position
    return i + 1; // Return the pivot's index
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Get the pivot index after partitioning
        int pi = partition(arr, low, high);
        
        // Recursively sort the left half
        quickSort(arr, low, pi - 1);
        // Recursively sort the right half
        quickSort(arr, pi + 1, high);
    }
}

// Helper function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test quick sort
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Compile & Run
$ gcc -o bin/quick-sort main.c
$ bin/quick-sort 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
$ 

Here is the Go implementation of Quick Sort, with detailed comments to aid understanding.

main.go
package main

import "fmt"

// partition implements partitioning, selecting the last element as the pivot
func partition(arr []int, low, high int) int {
    pivot := arr[high] // Select the last element as the pivot
    i := low - 1      // Boundary of the region with elements smaller than the pivot
    
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++ // Expand the region of smaller elements
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1] // Place the pivot in its correct position
    return i + 1 // Return the pivot's index
}

// quickSort implements the quick sort algorithm
func quickSort(arr []int, low, high int) {
    if low < high {
        // Get the pivot index after partitioning
        pi := partition(arr, low, high);
        
        // Recursively sort the left half
        quickSort(arr, low, pi-1)
        // Recursively sort the right half
        quickSort(arr, pi+1, high)
    }
}

// printArray prints the elements of an array
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // Example array
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("Original array: ");
    printArray(arr)
    
    quickSort(arr, 0, len(arr)-1)
    
    fmt.Print("Sorted array: ");
    printArray(arr)
}

$ gsk build -v
create quick-sort/bin/quick-sort-linux-amd64
$ ./bin/quick-sort-linux-amd64 
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

Summary

The core of Quick Sort is to achieve efficient sorting by selecting a pivot element to partition the array into two parts and recursively sorting them.

Copyright Notice: Freely reproduced, non-commercial, no derivatives, attribution, and keep the source.

Author: afxcn

Source: https://gostartkit.com/docs/algo/quick-sort

Date Published: June 28, 2025

Principle​

Steps​

Implementation​

Summary​

Principle

Steps

Implementation

Summary