Expand description
§Tartiblash algoritmlari (Sorting)
Darslik: 04-sorting/
| Algoritm | Eng yaxshi | O’rtacha | Eng yomon | Xotira | Barqaror? |
|---|---|---|---|---|---|
bubble_sort | O(n) | O(n²) | O(n²) | O(1) | Ha |
selection_sort | O(n²) | O(n²) | O(n²) | O(1) | Yo’q |
insertion_sort | O(n) | O(n²) | O(n²) | O(1) | Ha |
shell_sort | O(n log n) | ~O(n^1.3) | O(n²) | O(1) | Yo’q |
merge_sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ha |
quick_sort | O(n log n) | O(n log n) | O(n²)* | O(log n) | Yo’q |
heap_sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Yo’q |
counting_sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Ha |
radix_sort | O(d·(n+b)) | O(d·(n+b)) | O(d·(n+b)) | O(n+b) | Ha |
bucket_sort | O(n+k) | O(n+k) | O(n²) | O(n) | Ha |
* median-of-three pivot bilan O(n²) amalda deyarli uchramaydi.
Barqaror (stable) — teng qiymatli elementlarning dastlabki tartibi saqlanadi. Bu “avval ismga, keyin yoshga qarab saralash” kabi ko’p bosqichli saralashda muhim.
§Qaysi birini tanlash?
n kichikmi (< 32)? → insertion_sort (kesh do'sti, kam qo'shimcha xarajat)
Barqarorlik kerakmi? → merge_sort
Xotira taqchilmi? → heap_sort yoki quick_sort
Qiymatlar butun va tor oraliqda?→ counting_sort / radix_sort (n log n dan tez!)
Ishlab chiqarishda (production)?→ slice::sort (TimSort) / sort_unstable (pdqsort)Amalda Rustning
sort()vasort_unstable()idan foydalaning. Bu yerdagi kod — qanday ishlashini tushunish uchun.
Functions§
- bubble_
sort - Bubble sort — qo’shni elementlarni almashtira-almashtira “pufakchani” yuqoriga chiqarish.
- bucket_
sort - Bucket sort — qiymatlarni “chelaklarga” taqsimlab, har birini alohida tartiblash.
- counting_
sort - Counting sort — qiymatlarni sanab, o’z joyiga qo’yish.
- heap_
sort - Heap sort — max-heap (uyum) yordamida tartiblash.
- insertion_
sort - Insertion sort — qo’lingizdagi kartalarni terganingizdek.
- is_
sorted - Slice tartiblanganini (o’sish tartibida) tekshiradi.
- merge_
sort - Merge sort — “bo’l va hukmronlik qil” (divide & conquer) ning etaloni.
- quick_
sort - Quick sort — amaliyotdagi eng tez umumiy tartiblash algoritmi.
- radix_
sort - Radix sort (LSD, 256 lik asos) — sonlarni raqamma-raqam tartiblash.
- selection_
sort - Selection sort — qolgan qismdan eng kichigini topib, oldinga qo’yish.
- shell_
sort - Shell sort — insertion sortning “uzoq masofaga sakraydigan” versiyasi.