rust_algorithms/sorting/
mod.rs

1//! # Tartiblash algoritmlari (Sorting)
2//!
3//! Darslik: `04-sorting/`
4//!
5//! | Algoritm | Eng yaxshi | O'rtacha | Eng yomon | Xotira | Barqaror? |
6//! |---|---|---|---|---|---|
7//! | [`bubble_sort`] | O(n) | O(n²) | O(n²) | O(1) | Ha |
8//! | [`selection_sort`] | O(n²) | O(n²) | O(n²) | O(1) | Yo'q |
9//! | [`insertion_sort`] | O(n) | O(n²) | O(n²) | O(1) | Ha |
10//! | [`shell_sort`] | O(n log n) | ~O(n^1.3) | O(n²) | O(1) | Yo'q |
11//! | [`merge_sort`] | O(n log n) | O(n log n) | O(n log n) | O(n) | Ha |
12//! | [`quick_sort`] | O(n log n) | O(n log n) | O(n²)\* | O(log n) | Yo'q |
13//! | [`heap_sort`] | O(n log n) | O(n log n) | O(n log n) | O(1) | Yo'q |
14//! | [`counting_sort`] | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Ha |
15//! | [`radix_sort`] | O(d·(n+b)) | O(d·(n+b)) | O(d·(n+b)) | O(n+b) | Ha |
16//! | [`bucket_sort`] | O(n+k) | O(n+k) | O(n²) | O(n) | Ha |
17//!
18//! \* median-of-three pivot bilan O(n²) amalda deyarli uchramaydi.
19//!
20//! **Barqaror (stable)** — teng qiymatli elementlarning dastlabki tartibi saqlanadi.
21//! Bu "avval ismga, keyin yoshga qarab saralash" kabi ko'p bosqichli saralashda muhim.
22//!
23//! ## Qaysi birini tanlash?
24//!
25//! ```text
26//! n kichikmi (< 32)?              → insertion_sort (kesh do'sti, kam qo'shimcha xarajat)
27//! Barqarorlik kerakmi?            → merge_sort
28//! Xotira taqchilmi?               → heap_sort yoki quick_sort
29//! Qiymatlar butun va tor oraliqda?→ counting_sort / radix_sort (n log n dan tez!)
30//! Ishlab chiqarishda (production)?→ slice::sort (TimSort) / sort_unstable (pdqsort)
31//! ```
32//!
33//! > Amalda Rustning `sort()` va `sort_unstable()` idan foydalaning.
34//! > Bu yerdagi kod — **qanday ishlashini tushunish** uchun.
35
36mod efficient;
37mod linear_time;
38mod quadratic;
39
40pub use efficient::{heap_sort, merge_sort, quick_sort};
41pub use linear_time::{bucket_sort, counting_sort, radix_sort};
42pub use quadratic::{bubble_sort, insertion_sort, selection_sort, shell_sort};
43
44/// Slice tartiblanganini (o'sish tartibida) tekshiradi.
45///
46/// # Misol
47/// ```
48/// use rust_algorithms::sorting::is_sorted;
49///
50/// assert!(is_sorted(&[1, 2, 2, 3]));
51/// assert!(!is_sorted(&[3, 1]));
52/// ```
53pub fn is_sorted<T: Ord>(arr: &[T]) -> bool {
54    arr.windows(2).all(|w| w[0] <= w[1])
55}
rust_algorithms/sorting/mod.rs

rust_algorithms/sorting/
mod.rs
