rust_algorithms/sorting/

efficient.rs

//! O(n log n) — "kattalar ligasi": merge, quick, heap sort.

/// Merge sort — "bo'l va hukmronlik qil" (divide & conquer) ning etaloni.
///
/// **G'oya (3 qadam):**
/// 1. Massivni ikkiga bo'lamiz;
/// 2. Har ikkala yarmini **rekursiv** tartiblaymiz;
/// 3. Ikki tartiblangan yarmni bitta tartiblangan massivga **qo'shamiz** (merge).
///
/// Merge qadami chiziqli: ikkala yarmning boshiga barmoq qo'yib, kichigini olaveramiz.
///
/// - **Time:** O(n log n) — har doim (kirishga bog'liq emas).
/// - **Space:** O(n) — vaqtinchalik bufer.
/// - **Barqaror:** ha (`<=` sharti tufayli chapdagi element birinchi olinadi).
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::merge_sort;
///
/// let mut v = vec![38, 27, 43, 3, 9, 82, 10];
/// merge_sort(&mut v);
/// assert_eq!(v, [3, 9, 10, 27, 38, 43, 82]);
/// ```
pub fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }
    // Buferni bir marta ajratamiz (har rekursiyada emas) — bu tezlik uchun muhim.
    let mut buf = arr.to_vec();
    merge_sort_rec(arr, &mut buf);
}

fn merge_sort_rec<T: Ord + Clone>(arr: &mut [T], buf: &mut [T]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }
    let mid = n / 2;
    {
        let (left, right) = arr.split_at_mut(mid);
        let (bl, br) = buf.split_at_mut(mid);
        merge_sort_rec(left, bl);
        merge_sort_rec(right, br);
    }
    // Ikki tartiblangan yarmni buferga qo'shamiz, so'ng qaytarib ko'chiramiz.
    merge(&arr[..mid], &arr[mid..], buf);
    arr.clone_from_slice(&buf[..n]);
}

/// Ikki tartiblangan slicedan bitta tartiblangan ketma-ketlik yasaydi.
fn merge<T: Ord + Clone>(left: &[T], right: &[T], out: &mut [T]) {
    let (mut i, mut j, mut k) = (0, 0, 0);
    while i < left.len() && j < right.len() {
        // `<=` — barqarorlikning kaliti: tenglikda chapdagini olamiz.
        if left[i] <= right[j] {
            out[k] = left[i].clone();
            i += 1;
        } else {
            out[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        out[k] = left[i].clone();
        i += 1;
        k += 1;
    }
    while j < right.len() {
        out[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

/// Quick sort — amaliyotdagi eng tez umumiy tartiblash algoritmi.
///
/// **G'oya:** pivot (tayanch element) tanlaymiz va massivni ikkiga ajratamiz:
/// pivotdan kichiklar chapga, kattalar o'ngga. Pivot o'z **yakuniy** joyiga tushadi.
/// Keyin chap va o'ng qismlarni rekursiv tartiblaymiz.
///
/// Bu implementatsiyada ikkita muhim optimallashtirish bor:
/// - **median-of-three** pivot: tartiblangan massivda O(n²) ga tushib qolmaslik uchun;
/// - kichik bo'laklar (< 16) uchun **insertion sort**.
///
/// - **Time:** O(n log n) o'rtacha, O(n²) nazariy eng yomon holatda.
/// - **Space:** O(log n) — rekursiya stacki. **Barqaror emas.**
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::quick_sort;
///
/// let mut v = vec![10, 7, 8, 9, 1, 5];
/// quick_sort(&mut v);
/// assert_eq!(v, [1, 5, 7, 8, 9, 10]);
/// ```
pub fn quick_sort<T: Ord>(arr: &mut [T]) {
    const KICHIK: usize = 16;

    if arr.len() <= 1 {
        return;
    }
    if arr.len() <= KICHIK {
        super::insertion_sort(arr);
        return;
    }

    let p = partition(arr);
    let (left, right) = arr.split_at_mut(p);
    quick_sort(left);
    quick_sort(&mut right[1..]); // right[0] — pivot, u allaqachon o'z joyida
}

/// Lomuto bo'lish sxemasi. Qaytadi: pivotning yakuniy indeksi.
fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let last = arr.len() - 1;
    let pivot_idx = median_of_three(arr);
    arr.swap(pivot_idx, last); // pivotni vaqtincha oxirga olamiz

    let mut store = 0;
    for i in 0..last {
        if arr[i] <= arr[last] {
            arr.swap(i, store);
            store += 1;
        }
    }
    arr.swap(store, last); // pivotni o'z joyiga qaytaramiz
    store
}

/// Birinchi, o'rta va oxirgi elementlarning **medianasi** indeksini qaytaradi.
/// Bu allaqachon tartiblangan kirishlarda quick sortni O(n²) dan saqlaydi.
fn median_of_three<T: Ord>(arr: &[T]) -> usize {
    let (a, b, c) = (0, arr.len() / 2, arr.len() - 1);
    if arr[a] < arr[b] {
        if arr[b] < arr[c] {
            b
        } else if arr[a] < arr[c] {
            c
        } else {
            a
        }
    } else if arr[a] < arr[c] {
        a
    } else if arr[b] < arr[c] {
        c
    } else {
        b
    }
}

/// Heap sort — max-heap (uyum) yordamida tartiblash.
///
/// **G'oya (2 bosqich):**
/// 1. Massivni max-heapga aylantiramiz (`build_heap`, O(n));
/// 2. n marta: ildizdagi (eng katta) elementni oxirgi element bilan almashtiramiz,
///    heap hajmini bittaga kamaytiramiz va ildizni `sift_down` bilan joyiga tushiramiz.
///
/// **Kuchli tomoni:** qo'shimcha xotira **umuman kerak emas**, va eng yomon holat ham
/// kafolatlangan O(n log n) (quick sortdan farqli).
/// **Zaif tomoni:** keshga do'st emas — shuning uchun amalda quick sortdan sekinroq.
///
/// - **Time:** O(n log n) har doim, **Space:** O(1), **barqaror emas**.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::heap_sort;
///
/// let mut v = vec![12, 11, 13, 5, 6, 7];
/// heap_sort(&mut v);
/// assert_eq!(v, [5, 6, 7, 11, 12, 13]);
/// ```
pub fn heap_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    if n < 2 {
        return;
    }

    // 1) max-heap quramiz: oxirgi ota-tugundan boshlab yuqoriga
    for i in (0..n / 2).rev() {
        sift_down(arr, i, n);
    }

    // 2) maksimumni oxirga chiqarib boramiz
    for end in (1..n).rev() {
        arr.swap(0, end);
        sift_down(arr, 0, end);
    }
}

/// `root` dagi elementni `len` chegarasidagi heap ichida to'g'ri joyiga tushiradi.
fn sift_down<T: Ord>(arr: &mut [T], root: usize, len: usize) {
    let mut root = root;
    loop {
        let left = 2 * root + 1;
        if left >= len {
            break;
        }
        let right = left + 1;
        // ikki farzanddan kattasini tanlaymiz
        let mut largest = left;
        if right < len && arr[right] > arr[left] {
            largest = right;
        }
        if arr[root] >= arr[largest] {
            break; // heap sharti bajarildi
        }
        arr.swap(root, largest);
        root = largest;
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::sorting::is_sorted;
    use crate::util::Rng;

    fn holatlar() -> Vec<Vec<i64>> {
        let mut rng = Rng::new(777);
        vec![
            vec![],
            vec![1],
            vec![2, 1],
            (0..100).collect(),
            (0..100).rev().collect(),
            vec![7; 64],
            rng.vec(1000, -10_000, 10_000),
            rng.vec(257, 0, 3), // ko'p takrorlanuvchi qiymatlar
        ]
    }

    fn tekshir(sort: fn(&mut [i64])) {
        for mut v in holatlar() {
            let mut kutilgan = v.clone();
            kutilgan.sort_unstable();
            sort(&mut v);
            assert!(is_sorted(&v));
            assert_eq!(v, kutilgan);
        }
    }

    #[test]
    fn merge() {
        tekshir(merge_sort);
    }

    #[test]
    fn quick() {
        tekshir(quick_sort);
    }

    #[test]
    fn heap() {
        tekshir(heap_sort);
    }

    #[test]
    fn merge_barqaror() {
        let mut v = vec![(2, 'a'), (1, 'b'), (2, 'c'), (1, 'd'), (2, 'e')];
        merge_sort(&mut v);
        assert_eq!(v, vec![(1, 'b'), (1, 'd'), (2, 'a'), (2, 'c'), (2, 'e')]);
    }

    #[test]
    fn quick_tartiblangan_kirishda_ham_tez() {
        // median-of-three tufayli 100k tartiblangan element muammosiz o'tadi
        let mut v: Vec<i64> = (0..100_000).collect();
        quick_sort(&mut v);
        assert!(is_sorted(&v));
    }

    #[test]
    fn satrlarni_ham_tartiblaydi() {
        let mut v = vec!["olma", "anor", "banan", "uzum"];
        merge_sort(&mut v);
        assert_eq!(v, ["anor", "banan", "olma", "uzum"]);
    }
}