rust_algorithms/sorting/

linear_time.rs

//! Taqqoslashsiz (non-comparison) tartiblash: counting, radix, bucket.
//!
//! ## "n log n dan tez bo'lishi mumkinmi?"
//!
//! **Taqqoslashga asoslangan** har qanday algoritm uchun Ω(n log n) — buzib bo'lmaydigan
//! nazariy chegara (isbot: n! ta turli natija bor, har taqqoslash 1 bit ma'lumot beradi,
//! log₂(n!) ≈ n log n).
//!
//! Lekin biz elementlarni **taqqoslamasak**, balki ularning *qiymatini* to'g'ridan-to'g'ri
//! indeks sifatida ishlatsak — chegara ishlamaydi. Shu yerdagi uchta algoritm shunday qiladi.

/// Counting sort — qiymatlarni sanab, o'z joyiga qo'yish.
///
/// **G'oya:** har bir qiymat necha marta uchraganini sanaymiz, keyin prefiks yig'indi
/// orqali har bir qiymatning yakuniy o'rnini aniqlaymiz.
///
/// - **Shart:** qiymatlar butun va **tor oraliqda** bo'lishi kerak.
/// - **Time:** O(n + k), **Space:** O(n + k), bu yerda `k = max - min + 1`.
/// - **Barqaror:** ha (teskari yurish tufayli).
///
/// > Diqqat: `k` juda katta bo'lsa (masalan, `i32::MIN..i32::MAX`), bu algoritm
/// > gigabaytlab xotira so'raydi. Shuning uchun oraliq 10 milliondan katta bo'lsa
/// > funksiya `false` qaytaradi va massivga tegmaydi.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::counting_sort;
///
/// let mut v = vec![4, 2, 2, 8, 3, 3, 1];
/// assert!(counting_sort(&mut v));
/// assert_eq!(v, [1, 2, 2, 3, 3, 4, 8]);
/// ```
pub fn counting_sort(arr: &mut [i32]) -> bool {
    const MAX_ORALIQ: i64 = 10_000_000;

    if arr.len() < 2 {
        return true;
    }
    let min = *arr.iter().min().unwrap() as i64;
    let max = *arr.iter().max().unwrap() as i64;
    let k = max - min + 1;
    if k > MAX_ORALIQ {
        return false; // oraliq juda katta — merge/quick sort ishlating
    }

    // 1) sanaymiz
    let mut count = vec![0usize; k as usize];
    for &x in arr.iter() {
        count[(x as i64 - min) as usize] += 1;
    }

    // 2) prefiks yig'indi: count[i] = shu qiymatgacha bo'lgan elementlar soni
    for i in 1..count.len() {
        count[i] += count[i - 1];
    }

    // 3) oxiridan boshiga yurib joylashtiramiz — bu barqarorlikni saqlaydi
    let mut out = vec![0i32; arr.len()];
    for &x in arr.iter().rev() {
        let idx = (x as i64 - min) as usize;
        count[idx] -= 1;
        out[count[idx]] = x;
    }

    arr.copy_from_slice(&out);
    true
}

/// Radix sort (LSD, 256 lik asos) — sonlarni **raqamma-raqam** tartiblash.
///
/// **G'oya:** eng past baytdan boshlab, har bir bayt bo'yicha counting sort qilamiz.
/// Counting sort barqaror bo'lgani uchun oldingi bosqichlar natijasi buzilmaydi —
/// 8 ta bosqichdan keyin butun `u64` tartiblangan bo'ladi.
///
/// - **Time:** O(d·(n + b)) = `u64` uchun 8·(n + 256) ≈ **O(n)**.
/// - **Space:** O(n + b), **barqaror**.
///
/// Millionlab butun sonlarni tartiblashda `sort_unstable` dan ham tez bo'lishi mumkin.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::radix_sort;
///
/// let mut v: Vec<u64> = vec![170, 45, 75, 90, 802, 24, 2, 66];
/// radix_sort(&mut v);
/// assert_eq!(v, [2, 24, 45, 66, 75, 90, 170, 802]);
/// ```
///
/// **Manfiy sonlar-chi?** `i64` ni `(x as i64 ^ i64::MIN) as u64` ko'rinishida
/// almashtirsangiz (belgi bitini teskari qilib), tartib saqlanadi.
pub fn radix_sort(arr: &mut [u64]) {
    if arr.len() < 2 {
        return;
    }
    let n = arr.len();
    let mut buf = vec![0u64; n];

    for bayt in 0..8 {
        let siljish = bayt * 8;

        // shu bayt bo'yicha sanaymiz
        let mut count = [0usize; 256];
        for &x in arr.iter() {
            count[((x >> siljish) & 0xFF) as usize] += 1;
        }

        // bu baytda hamma bir xilmi? unda bosqichni o'tkazib yuboramiz
        if count.contains(&n) {
            continue;
        }

        // prefiks yig'indi
        let mut sum = 0usize;
        for c in count.iter_mut() {
            let hozirgi = *c;
            *c = sum;
            sum += hozirgi;
        }

        // barqaror joylashtirish
        for &x in arr.iter() {
            let idx = ((x >> siljish) & 0xFF) as usize;
            buf[count[idx]] = x;
            count[idx] += 1;
        }
        arr.copy_from_slice(&buf);
    }
}

/// Bucket sort — qiymatlarni "chelaklarga" taqsimlab, har birini alohida tartiblash.
///
/// **G'oya:** qiymatlar oralig'ini `n` ta teng bo'lakka bo'lamiz. Har bir element
/// o'z chelagiga tushadi; chelaklar ichi insertion sort bilan tartiblanadi;
/// oxirida chelaklar ketma-ket birlashtiriladi.
///
/// - **Time:** O(n + k) — qiymatlar **tekis taqsimlangan** bo'lsa; eng yomon holatda O(n²)
///   (hamma element bitta chelakka tushsa).
/// - **Space:** O(n), **barqaror**.
///
/// # Misol
/// ```
/// use rust_algorithms::sorting::bucket_sort;
///
/// let mut v = vec![0.42, 0.32, 0.75, 0.12, 0.99, 0.51];
/// bucket_sort(&mut v);
/// assert_eq!(v, [0.12, 0.32, 0.42, 0.51, 0.75, 0.99]);
/// ```
pub fn bucket_sort(arr: &mut [f64]) {
    let n = arr.len();
    if n < 2 {
        return;
    }

    let min = arr.iter().cloned().fold(f64::INFINITY, f64::min);
    let max = arr.iter().cloned().fold(f64::NEG_INFINITY, f64::max);
    if !min.is_finite() || !max.is_finite() || min == max {
        // NaN/cheksizlik yoki hamma qiymat teng — oddiy yo'l bilan tartiblaymiz
        arr.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
        return;
    }

    let mut chelaklar: Vec<Vec<f64>> = vec![Vec::new(); n];
    let kenglik = (max - min) / n as f64;
    for &x in arr.iter() {
        let mut idx = ((x - min) / kenglik) as usize;
        if idx >= n {
            idx = n - 1; // maksimal qiymat uchun
        }
        chelaklar[idx].push(x);
    }

    let mut k = 0usize;
    for chelak in chelaklar.iter_mut() {
        chelak.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
        for &x in chelak.iter() {
            arr[k] = x;
            k += 1;
        }
    }
}

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

    #[test]
    fn counting_ishlaydi() {
        let mut rng = Rng::new(11);
        for _ in 0..20 {
            let mut v: Vec<i32> = rng
                .vec(300, -50, 50)
                .into_iter()
                .map(|x| x as i32)
                .collect();
            let mut kutilgan = v.clone();
            kutilgan.sort_unstable();
            assert!(counting_sort(&mut v));
            assert_eq!(v, kutilgan);
        }
        let mut bosh: Vec<i32> = vec![];
        assert!(counting_sort(&mut bosh));
    }

    #[test]
    fn counting_juda_katta_oraliqda_rad_etadi() {
        let mut v = vec![i32::MIN, 0, i32::MAX];
        assert!(!counting_sort(&mut v));
        assert_eq!(v, vec![i32::MIN, 0, i32::MAX]); // massivga tegilmagan
    }

    #[test]
    fn radix_ishlaydi() {
        let mut rng = Rng::new(22);
        for n in [0usize, 1, 2, 500] {
            let mut v: Vec<u64> = (0..n).map(|_| rng.next_u64() % 1_000_000).collect();
            let mut kutilgan = v.clone();
            kutilgan.sort_unstable();
            radix_sort(&mut v);
            assert_eq!(v, kutilgan);
        }
    }

    #[test]
    fn radix_katta_sonlarda() {
        let mut rng = Rng::new(33);
        let mut v: Vec<u64> = (0..2000).map(|_| rng.next_u64()).collect();
        let mut kutilgan = v.clone();
        kutilgan.sort_unstable();
        radix_sort(&mut v);
        assert_eq!(v, kutilgan);
    }

    #[test]
    fn bucket_ishlaydi() {
        let mut rng = Rng::new(44);
        let mut v: Vec<f64> = (0..500)
            .map(|_| rng.next_u64() as f64 / u64::MAX as f64)
            .collect();
        bucket_sort(&mut v);
        assert!(v.windows(2).all(|w| w[0] <= w[1]));

        let mut teng = vec![1.5; 10];
        bucket_sort(&mut teng);
        assert_eq!(teng, vec![1.5; 10]);

        let mut kichik = vec![2.0];
        bucket_sort(&mut kichik);
        assert_eq!(kichik, vec![2.0]);
    }

    #[test]
    fn hammasi_bir_xil_natija_beradi() {
        let mut rng = Rng::new(55);
        let asl: Vec<i32> = rng.vec(400, 0, 999).into_iter().map(|x| x as i32).collect();

        let mut a = asl.clone();
        assert!(counting_sort(&mut a));

        let mut b: Vec<u64> = asl.iter().map(|&x| x as u64).collect();
        radix_sort(&mut b);

        assert!(is_sorted(&a));
        assert_eq!(a.iter().map(|&x| x as u64).collect::<Vec<_>>(), b);
    }
}