Quick Sort

1def quick_sort(a, low=0, high=None):2    if high is None:3        high = len(a) - 14    if low < high:5        p = partition(a, low, high)6        quick_sort(a, low, p - 1)7        quick_sort(a, p + 1, high)8    return a9
10
11def partition(a, low, high):12    # Lomuto partition: everything < pivot moves left of it13    pivot = a[high]14    i = low15    for j in range(low, high):16        if a[j] < pivot:17            a[i], a[j] = a[j], a[i]18            i += 119    a[i], a[high] = a[high], a[i]20    return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)

1function quickSort(a, lo = 0, hi = a.length - 1) {2    if (lo >= hi) return a;3    const p = partition(a, lo, hi);4    quickSort(a, lo, p - 1);5    quickSort(a, p + 1, hi);6    return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11    const pivot = a[hi];12    let i = lo;13    for (let j = lo; j < hi; j++) {14        if (a[j] < pivot) {15            [a[i], a[j]] = [a[j], a[i]];16            i++;17        }18    }19    [a[i], a[hi]] = [a[hi], a[i]];20    return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));

1import java.util.Arrays;2
3public class Main {4    static void quickSort(int[] arr, int low, int high) {5        if (low >= high) return;6        int p = partition(arr, low, high);7        quickSort(arr, low, p - 1);8        quickSort(arr, p + 1, high);9    }10
11    // Lomuto partition: last element is the pivot12    static int partition(int[] arr, int low, int high) {13        int pivot = arr[high];14        int i = low - 1;15        for (int j = low; j < high; j++) {16            if (arr[j] < pivot) swap(arr, ++i, j);17        }18        swap(arr, i + 1, high);19        return i + 1;20    }21
22    static void swap(int[] arr, int a, int b) {23        int tmp = arr[a];24        arr[a] = arr[b];25        arr[b] = tmp;26    }27
28    public static void main(String[] args) {29        int[] arr = {10, 7, 8, 9, 1, 5};30        System.out.println("Before: " + Arrays.toString(arr));31        quickSort(arr, 0, arr.length - 1);32        System.out.println("After:  " + Arrays.toString(arr));33    }34}

1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12    int pivot = a[hi];13    int i = lo;14    for (int j = lo; j < hi; ++j) {15        if (a[j] < pivot) std::swap(a[i++], a[j]);16    }17    std::swap(a[i], a[hi]);18    return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22    if (lo >= hi) return;23    int p = partition(a, lo, hi);24    quickSort(a, lo, p - 1);25    quickSort(a, p + 1, hi);26}27
28int main() {29    std::vector<int> data = {10, 7, 8, 9, 1, 5};30    std::cout << "Before: ";31    printVec(data);32    quickSort(data, 0, static_cast<int>(data.size()) - 1);33    std::cout << "After:  ";34    printVec(data);35    return 0;36}

1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void swap(int* x, int* y) {9    int tmp = *x;10    *x = *y;11    *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16    int pivot = a[hi];17    int i = lo;18    for (int j = lo; j < hi; j++) {19        if (a[j] < pivot) swap(&a[i++], &a[j]);20    }21    swap(&a[i], &a[hi]);22    return i;23}24
25void quickSort(int a[], int lo, int hi) {26    if (lo >= hi) return;27    int p = partition(a, lo, hi);28    quickSort(a, lo, p - 1);29    quickSort(a, p + 1, hi);30}31
32int main(void) {33    int data[] = {10, 7, 8, 9, 1, 5};34    int n = sizeof(data) / sizeof(data[0]);35    printf("Before: ");36    printArr(data, n);37    quickSort(data, 0, n - 1);38    printf("After:  ");39    printArr(data, n);40    return 0;41}