Array: [10, 80, 30, 90, 40, 50, 70]
                            pivô = 70

Particionamento (Lomuto):
  i aponta para onde colocar o próximo menor que pivô

  [10, 80, 30, 90, 40, 50, 70]
   10<70 → troca posição 0 com 0: [10, 80, 30, 90, 40, 50, 70]
   80>70 → nada
   30<70 → troca posição 1 com 2: [10, 30, 80, 90, 40, 50, 70]
   90>70 → nada
   40<70 → troca posição 2 com 4: [10, 30, 40, 90, 80, 50, 70]
   50<70 → troca posição 3 com 5: [10, 30, 40, 50, 80, 90, 70]
   Coloca pivô na posição 4:      [10, 30, 40, 50, 70, 90, 80]
                                          ↑ menores ↑ ↑ maiores ↑

Recursão nas duas partições:
  [10, 30, 40, 50]  e  [90, 80]
  ... continua até partições de tamanho 1

const std = @import("std");

/// Quick Sort usando particionamento de Lomuto.
pub fn quickSort(comptime T: type, items: []T) void {
    if (items.len <= 1) return;
    quickSortHelper(T, items, 0, items.len - 1);
}

fn quickSortHelper(comptime T: type, items: []T, low: usize, high: usize) void {
    if (low >= high) return;

    const pivot_idx = partitionLomuto(T, items, low, high);

    // Recursão nas partições
    if (pivot_idx > 0) quickSortHelper(T, items, low, pivot_idx - 1);
    if (pivot_idx < items.len - 1) quickSortHelper(T, items, pivot_idx + 1, high);
}

/// Particionamento de Lomuto: usa o último elemento como pivô.
fn partitionLomuto(comptime T: type, items: []T, low: usize, high: usize) usize {
    const pivot = items[high];
    var i: usize = low;

    var j: usize = low;
    while (j < high) : (j += 1) {
        if (items[j] <= pivot) {
            const temp = items[i];
            items[i] = items[j];
            items[j] = temp;
            i += 1;
        }
    }

    // Coloca o pivô na posição correta
    const temp = items[i];
    items[i] = items[high];
    items[high] = temp;

    return i;
}

/// Quick Sort com particionamento de Hoare (mais eficiente).
pub fn quickSortHoare(comptime T: type, items: []T) void {
    if (items.len <= 1) return;
    quickSortHoareHelper(T, items, 0, items.len - 1);
}

fn quickSortHoareHelper(comptime T: type, items: []T, low: usize, high: usize) void {
    if (low >= high) return;

    const p = partitionHoare(T, items, low, high);
    if (p > 0) quickSortHoareHelper(T, items, low, p);
    quickSortHoareHelper(T, items, p + 1, high);
}

/// Particionamento de Hoare: dois ponteiros convergindo ao centro.
fn partitionHoare(comptime T: type, items: []T, low: usize, high: usize) usize {
    const pivot = items[low + (high - low) / 2];
    var i: usize = if (low > 0) low - 1 else 0;
    var j: usize = high + 1;

    if (low == 0) {
        i = 0;
        // Ajuste especial para quando low é 0
        while (true) {
            j -= 1;
            while (items[j] > pivot) : (j -= 1) {}
            while (items[i] < pivot) : (i += 1) {}
            if (i >= j) return j;
            const temp = items[i];
            items[i] = items[j];
            items[j] = temp;
            i += 1;
        }
    }

    while (true) {
        i += 1;
        while (items[i] < pivot) : (i += 1) {}
        j -= 1;
        while (items[j] > pivot) : (j -= 1) {}
        if (i >= j) return j;
        const temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
}

/// Quick Sort com mediana de três como pivô (anti pior caso).
pub fn quickSortMediana3(comptime T: type, items: []T) void {
    if (items.len <= 1) return;
    qsMediana3(T, items, 0, items.len - 1);
}

fn qsMediana3(comptime T: type, items: []T, low: usize, high: usize) void {
    if (high <= low) return;

    // Para partições pequenas, usa insertion sort
    if (high - low < 10) {
        var i: usize = low + 1;
        while (i <= high) : (i += 1) {
            const chave = items[i];
            var j: usize = i;
            while (j > low and items[j - 1] > chave) {
                items[j] = items[j - 1];
                j -= 1;
            }
            items[j] = chave;
        }
        return;
    }

    // Mediana de três: primeiro, meio, último
    const meio = low + (high - low) / 2;
    if (items[meio] < items[low]) {
        const t = items[low];
        items[low] = items[meio];
        items[meio] = t;
    }
    if (items[high] < items[low]) {
        const t = items[low];
        items[low] = items[high];
        items[high] = t;
    }
    if (items[high] < items[meio]) {
        const t = items[meio];
        items[meio] = items[high];
        items[high] = t;
    }
    // Mediana está em items[meio], move para high-1
    const t = items[meio];
    items[meio] = items[high - 1];
    items[high - 1] = t;

    const pivot_idx = partitionLomuto(T, items, low, high - 1);
    if (pivot_idx > 0) qsMediana3(T, items, low, pivot_idx - 1);
    if (pivot_idx < items.len - 1) qsMediana3(T, items, pivot_idx + 1, high);
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    var numeros = [_]i32{ 10, 80, 30, 90, 40, 50, 70 };

    try stdout.print("Original: ", .{});
    for (numeros) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});

    quickSort(i32, &numeros);

    try stdout.print("Ordenado: ", .{});
    for (numeros) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});
}