Sắp xếp nhanh (Quick Sort)

// Quick sort, in place: Hoare partition around a median-of-three pivot.
// Pick a pivot, move the small values left and the big values right, then sort each side.

/**
 * Sorts `values` in ascending order, in place.
 * Not stable: equal values may end up in a different order than they started.
 *
 * @param {number[]} values the array to sort
 * @returns {void}
 */
export function quickSort(values) {
  sortRange(values, 0, values.length - 1);
}

/**
 * Sorts values[lo..hi] (both ends included).
 * Recurses into the smaller side and loops on the bigger one, so the call stack never grows
 * past about log2(n) frames — even when the pivots are unlucky.
 *
 * @param {number[]} values
 * @param {number} lo
 * @param {number} hi
 */
function sortRange(values, lo, hi) {
  while (lo < hi) {
    const split = hoarePartition(values, lo, hi);
    const leftSize = split - lo + 1;
    const rightSize = hi - split;

    if (leftSize < rightSize) {
      sortRange(values, lo, split); // small side: recursion
      lo = split + 1; // big side: next turn of the loop
    } else {
      sortRange(values, split + 1, hi);
      hi = split;
    }
  }
}

/**
 * Hoare partition of values[lo..hi]. Returns `split` with lo <= split < hi such that
 * every value in [lo, split] is <= every value in [split + 1, hi].
 * Both sides are non-empty, so each one is strictly smaller than the range we started with.
 *
 * @param {number[]} values
 * @param {number} lo
 * @param {number} hi
 * @returns {number}
 */
function hoarePartition(values, lo, hi) {
  const pivot = medianOfThree(values, lo, hi);
  let i = lo - 1;
  let j = hi + 1;

  while (true) {
    // Walk i right past values that already belong on the left…
    do {
      i++;
    } while (values[i] < pivot);
    // …and j left past values that already belong on the right.
    do {
      j--;
    } while (values[j] > pivot);

    if (i >= j) return j; // the two walks met: everything is on its side
    swap(values, i, j); // both are on the wrong side — trade places
  }
}

/**
 * Puts values[lo], values[mid] and values[hi] in order and returns the middle one.
 * On sorted or reversed input this picks the true median, which is exactly where
 * "always take the first element" falls to O(n²).
 *
 * @param {number[]} values
 * @param {number} lo
 * @param {number} hi
 * @returns {number}
 */
function medianOfThree(values, lo, hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  if (values[mid] < values[lo]) swap(values, mid, lo);
  if (values[hi] < values[lo]) swap(values, hi, lo);
  if (values[hi] < values[mid]) swap(values, hi, mid);
  return values[mid];
}

/**
 * @param {number[]} values
 * @param {number} a
 * @param {number} b
 */
function swap(values, a, b) {
  [values[a], values[b]] = [values[b], values[a]];
}

# Quick sort, in place: Hoare partition around a median-of-three pivot.
# Pick a pivot, move the small values left and the big values right, then sort each side.
from typing import List


def quick_sort(values: List[int]) -> None:
    """Sort values in ascending order, in place.

    Not stable: equal values may end up in a different order than they started.
    """
    _sort_range(values, 0, len(values) - 1)


def _sort_range(values: List[int], lo: int, hi: int) -> None:
    """Sort values[lo..hi] (both ends included).

    Recurse into the smaller side and loop on the bigger one, so the call
    stack never grows past about log2(n) frames — even with unlucky pivots.
    """
    while lo < hi:
        split = _hoare_partition(values, lo, hi)
        left_size = split - lo + 1
        right_size = hi - split

        if left_size < right_size:
            _sort_range(values, lo, split)  # small side: recursion
            lo = split + 1  # big side: next turn of the loop
        else:
            _sort_range(values, split + 1, hi)
            hi = split


def _hoare_partition(values: List[int], lo: int, hi: int) -> int:
    """Hoare partition of values[lo..hi].

    Return split with lo <= split < hi such that every value in [lo, split]
    is <= every value in [split + 1, hi]. Both sides are non-empty, so each
    one is strictly smaller than the range we started with.
    """
    pivot = _median_of_three(values, lo, hi)
    i = lo - 1
    j = hi + 1

    while True:
        # Walk i right past values that already belong on the left…
        i += 1
        while values[i] < pivot:
            i += 1
        # …and j left past values that already belong on the right.
        j -= 1
        while values[j] > pivot:
            j -= 1

        if i >= j:
            return j  # the two walks met: everything is on its side
        values[i], values[j] = values[j], values[i]  # both on the wrong side — trade places


def _median_of_three(values: List[int], lo: int, hi: int) -> int:
    """Put values[lo], values[mid], values[hi] in order and return the middle one.

    On sorted or reversed input this picks the true median, which is exactly
    where "always take the first element" falls to O(n²).
    """
    mid = lo + (hi - lo) // 2
    if values[mid] < values[lo]:
        values[mid], values[lo] = values[lo], values[mid]
    if values[hi] < values[lo]:
        values[hi], values[lo] = values[lo], values[hi]
    if values[hi] < values[mid]:
        values[hi], values[mid] = values[mid], values[hi]
    return values[mid]

/**
 * Quick sort, in place: Hoare partition around a median-of-three pivot.
 * Pick a pivot, move the small values left and the big values right, then sort each side.
 */
public final class QuickSort {
    private QuickSort() {
    }

    /**
     * Sorts values in ascending order, in place.
     * Not stable: equal values may end up in a different order than they started.
     */
    public static void quickSort(int[] values) {
        sortRange(values, 0, values.length - 1);
    }

    /**
     * Sorts values[lo..hi] (both ends included).
     * Recurses into the smaller side and loops on the bigger one, so the call stack never grows
     * past about log2(n) frames — even when the pivots are unlucky.
     */
    private static void sortRange(int[] values, int lo, int hi) {
        while (lo < hi) {
            int split = hoarePartition(values, lo, hi);
            int leftSize = split - lo + 1;
            int rightSize = hi - split;

            if (leftSize < rightSize) {
                sortRange(values, lo, split); // small side: recursion
                lo = split + 1; // big side: next turn of the loop
            } else {
                sortRange(values, split + 1, hi);
                hi = split;
            }
        }
    }

    /**
     * Hoare partition of values[lo..hi]. Returns split with lo <= split < hi such that
     * every value in [lo, split] is <= every value in [split + 1, hi].
     * Both sides are non-empty, so each one is strictly smaller than the range we started with.
     */
    private static int hoarePartition(int[] values, int lo, int hi) {
        int pivot = medianOfThree(values, lo, hi);
        int i = lo - 1;
        int j = hi + 1;

        while (true) {
            // Walk i right past values that already belong on the left…
            do {
                i++;
            } while (values[i] < pivot);
            // …and j left past values that already belong on the right.
            do {
                j--;
            } while (values[j] > pivot);

            if (i >= j) {
                return j; // the two walks met: everything is on its side
            }
            swap(values, i, j); // both are on the wrong side — trade places
        }
    }

    /**
     * Puts values[lo], values[mid] and values[hi] in order and returns the middle one.
     * On sorted or reversed input this picks the true median, which is exactly where
     * "always take the first element" falls to O(n²).
     */
    private static int medianOfThree(int[] values, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] < values[lo]) {
            swap(values, mid, lo);
        }
        if (values[hi] < values[lo]) {
            swap(values, hi, lo);
        }
        if (values[hi] < values[mid]) {
            swap(values, hi, mid);
        }
        return values[mid];
    }

    private static void swap(int[] values, int a, int b) {
        int tmp = values[a];
        values[a] = values[b];
        values[b] = tmp;
    }
}

// Quick sort, in place: Hoare partition around a median-of-three pivot.
// Pick a pivot, move the small values left and the big values right, then sort each side.
// (In real code reach for std::sort — an introsort built on the same idea.)
#include <utility>
#include <vector>

// Puts values[lo], values[mid] and values[hi] in order and returns the middle one.
// On sorted or reversed input this picks the true median, which is exactly where
// "always take the first element" falls to O(n²).
int medianOfThree(std::vector<int>& values, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (values[mid] < values[lo]) {
        std::swap(values[mid], values[lo]);
    }
    if (values[hi] < values[lo]) {
        std::swap(values[hi], values[lo]);
    }
    if (values[hi] < values[mid]) {
        std::swap(values[hi], values[mid]);
    }
    return values[mid];
}

// Hoare partition of values[lo..hi]. Returns split with lo <= split < hi such that
// every value in [lo, split] is <= every value in [split + 1, hi].
// Both sides are non-empty, so each one is strictly smaller than the range we started with.
int hoarePartition(std::vector<int>& values, int lo, int hi) {
    int pivot = medianOfThree(values, lo, hi);
    int i = lo - 1;
    int j = hi + 1;

    while (true) {
        // Walk i right past values that already belong on the left…
        do {
            ++i;
        } while (values[i] < pivot);
        // …and j left past values that already belong on the right.
        do {
            --j;
        } while (values[j] > pivot);

        if (i >= j) {
            return j;  // the two walks met: everything is on its side
        }
        std::swap(values[i], values[j]);  // both are on the wrong side — trade places
    }
}

// Sorts values[lo..hi] (both ends included).
// Recurses into the smaller side and loops on the bigger one, so the call stack never grows
// past about log2(n) frames — even when the pivots are unlucky.
void sortRange(std::vector<int>& values, int lo, int hi) {
    while (lo < hi) {
        int split = hoarePartition(values, lo, hi);
        int leftSize = split - lo + 1;
        int rightSize = hi - split;

        if (leftSize < rightSize) {
            sortRange(values, lo, split);  // small side: recursion
            lo = split + 1;                // big side: next turn of the loop
        } else {
            sortRange(values, split + 1, hi);
            hi = split;
        }
    }
}

// Sorts values in ascending order, in place.
// Not stable: equal values may end up in a different order than they started.
void quickSort(std::vector<int>& values) {
    sortRange(values, 0, static_cast<int>(values.size()) - 1);
}