rust_algorithms/sorting/

quadratic.rs

//! O(n²) oilasidagi "o'quv" algoritmlari + Shell sort.
//!
//! Ular sekin, lekin *g'oyasi* keyingi hamma narsaning poydevori.

/// Bubble sort — qo'shni elementlarni almashtira-almashtira "pufakchani" yuqoriga chiqarish.
///
/// **G'oya:** massiv bo'ylab yurib, `arr[j] > arr[j+1]` bo'lsa almashtiramiz.
/// Bitta to'liq yurishdan keyin eng katta element **oxirida** bo'ladi.
///
/// Bu yerda optimallashtirilgan variant: agar bitta yurishda hech narsa almashmasa,
/// massiv allaqachon tartiblangan — to'xtaymiz (shuning uchun eng yaxshi holat O(n)).
///
/// - **Time:** O(n) / O(n²) / O(n²), **Space:** O(1), **barqaror**.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::bubble_sort;
///
/// let mut v = vec![5, 1, 4, 2, 8];
/// bubble_sort(&mut v);
/// assert_eq!(v, [1, 2, 4, 5, 8]);
/// ```
pub fn bubble_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false;
        // Har yurishdan keyin oxirgi `i` ta element o'z joyida — ularga tegmaymiz.
        for j in 0..n.saturating_sub(i + 1) {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
                swapped = true;
            }
        }
        if !swapped {
            break; // allaqachon tartiblangan
        }
    }
}

/// Selection sort — qolgan qismdan eng kichigini topib, oldinga qo'yish.
///
/// **G'oya:** `i` -pozitsiya uchun `i..n` oralig'idagi minimumni topamiz va almashtiramiz.
///
/// Almashtirishlar soni har doim **eng ko'pi bilan n ta** — yozish (write) qimmat
/// bo'lgan xotirada (masalan, flash) shuning uchun foydali.
///
/// - **Time:** O(n²) har doim, **Space:** O(1), **barqaror emas**.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::selection_sort;
///
/// let mut v = vec![64, 25, 12, 22, 11];
/// selection_sort(&mut v);
/// assert_eq!(v, [11, 12, 22, 25, 64]);
/// ```
pub fn selection_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    for i in 0..n {
        let mut min_idx = i;
        for j in (i + 1)..n {
            if arr[j] < arr[min_idx] {
                min_idx = j;
            }
        }
        if min_idx != i {
            arr.swap(i, min_idx);
        }
    }
}

/// Insertion sort — qo'lingizdagi kartalarni terganingizdek.
///
/// **G'oya:** chap tomon har doim tartiblangan. Navbatdagi elementni olib,
/// chapdagi tartiblangan qismning to'g'ri joyiga "suqib" qo'yamiz.
///
/// **Amaliy ahamiyati katta:** kichik massivlarda (n < 32) va **deyarli tartiblangan**
/// ma'lumotlarda hamma narsadan tez. Shuning uchun TimSort/pdqsort ichida ishlatiladi.
///
/// - **Time:** O(n) (tartiblangan bo'lsa) / O(n²), **Space:** O(1), **barqaror**.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::insertion_sort;
///
/// let mut v = vec![12, 11, 13, 5, 6];
/// insertion_sort(&mut v);
/// assert_eq!(v, [5, 6, 11, 12, 13]);
/// ```
pub fn insertion_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        // Elementni o'z joyiga yetguncha chapga surib boramiz.
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}

/// Shell sort — insertion sortning "uzoq masofaga sakraydigan" versiyasi.
///
/// **G'oya:** avval bir-biridan `gap` masofada turgan elementlarni tartiblaymiz,
/// keyin `gap` ni kichraytira boramiz. Katta gaplar elementlarni tez o'z
/// hududiga olib keladi, oxirgi `gap = 1` esa deyarli tayyor massivni tugatadi.
///
/// Bu yerda Knuth ketma-ketligi ishlatilgan: 1, 4, 13, 40, 121… (`3h+1`).
///
/// - **Time:** ~O(n^1.3) amalda, **Space:** O(1), **barqaror emas**.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::shell_sort;
///
/// let mut v = vec![23, 12, 1, 8, 34, 54, 2, 3];
/// shell_sort(&mut v);
/// assert_eq!(v, [1, 2, 3, 8, 12, 23, 34, 54]);
/// ```
pub fn shell_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    if n < 2 {
        return;
    }

    // Knuth ketma-ketligi bo'yicha eng katta gapni topamiz
    let mut gap = 1usize;
    while gap < n / 3 {
        gap = gap * 3 + 1;
    }

    while gap >= 1 {
        for i in gap..n {
            let mut j = i;
            while j >= gap && arr[j - gap] > arr[j] {
                arr.swap(j - gap, j);
                j -= gap;
            }
        }
        if gap == 1 {
            break;
        }
        gap /= 3;
    }
}

#[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(20_26);
        vec![
            vec![],
            vec![1],
            vec![2, 1],
            vec![1, 2, 3, 4, 5],            // tartiblangan
            vec![5, 4, 3, 2, 1],            // teskari
            vec![3, 3, 3, 3],               // hammasi teng
            vec![-5, 0, 7, -2, 9, 9, -100], // manfiylar va takrorlar
            rng.vec(200, -1000, 1000),      // tasodifiy
        ]
    }

    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), "tartiblanmadi: {v:?}");
            assert_eq!(v, kutilgan);
        }
    }

    #[test]
    fn bubble() {
        tekshir(bubble_sort);
    }

    #[test]
    fn selection() {
        tekshir(selection_sort);
    }

    #[test]
    fn insertion() {
        tekshir(insertion_sort);
    }

    #[test]
    fn shell() {
        tekshir(shell_sort);
    }

    #[test]
    fn bubble_barqaror() {
        // (kalit, tartib raqami) — kalit bo'yicha saralaganda raqamlar tartibi saqlanishi kerak
        let mut v = vec![(1, 'a'), (0, 'b'), (1, 'c'), (0, 'd')];
        bubble_sort(&mut v);
        assert_eq!(v, vec![(0, 'b'), (0, 'd'), (1, 'a'), (1, 'c')]);
    }
}