Function counting_sort 

pub fn counting_sort(arr: &mut [i32]) -> bool

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]);