Sorting alqoritmləri
Sorting alqoritmləri iki ailəyə bölünür.
Sadə, `O(n²)` ailəsi — kod qısadır, kiçik massivlərdə praktikada sürətlidir:
- Bubble sort — qonşuları müqayisə edib yerlərini dəyişir; "heç bir dəyişiklik olmadı" bayrağı ilə artıq sıralanmış massivdə
O(n)verir. Real kodda demək olar ki, istifadə olunmur, yalnız tədris üçündür - Insertion sort — hər elementi soldakı sıralanmış hissəyə "yerləşdirir". Demək olar sıralanmış datada çox sürətlidir (
O(n)-ə yaxın) və məhz buna görə real kitabxanalarda kiçik hissələr üçün istifadə olunur - Selection sort — hər dövrədə ən kiçiyi tapıb önə qoyur. Həmişə
O(n²)— data nə qədər yaxşı olsa da fərq etmir. Tək üstünlüyü: swap sayı minimaldır (O(n)), ona görə yazma əməliyyatı çox bahalı olan yaddaşda mənası var
Səmərəli, `O(n log n)` ailəsi:
- Merge sort — massivi ikiyə bölür, hər hissəni sıralayır, birləşdirir. Bütün hallarda
O(n log n), stabil, ammaO(n)əlavə yaddaş istəyir. Linked list-də və xarici (disk üzərində) sorting-də əvəzsizdir - Quicksort — pivot seçir, kiçikləri sola, böyükləri sağa yığır, sonra hissələri təkrar sıralayır. Ortalama
O(n log n)və praktikada ən sürətlisi, amma pis pivot seçimindəO(n²). Stabil deyil - Heap sort — massivdən heap qurub bir-bir ən böyüyü çıxarır. Bütün hallarda
O(n log n)vəO(1)əlavə yaddaş, amma cache-ə dostluğu az olduğuna görə praktikada quicksort-dan yavaşdır. Stabil deyil
| Alqoritm | Best | Average | Worst | Əlavə yaddaş | Stabil? |
|---|---|---|---|---|---|
| Bubble sort | O(n) — bayraqla | O(n²) | O(n²) | O(1) | Bəli |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Bəli |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | Xeyr |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Bəli |
| Quicksort | O(n log n) | O(n log n) | O(n²) — pis pivot | O(log n) — rekursiya | Xeyr |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Xeyr |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Bəli — düzgün yazılsa |
Niyə `O(n log n)`-dən yaxşısı mümkün deyil? Bu, interview-da "nəzəri dərinlik" yoxlayan sualdır və cavabı gözlədiyindən sadədir.
Müqayisə əsaslı sorting alqoritmini qərar ağacı kimi təsəvvür et: hər müqayisə iki nəticədən birini verir, yəni ağac ikiliyə budaqlanır. n elementin n! mümkün düzülüşü var, deməli ağacın ən azı n! yarpağı olmalıdır — hər mümkün cavab üçün bir yarpaq. Hündürlüyü h olan ikili ağacın ən çoxu 2^h yarpağı var, deməli 2^h ≥ n!, yəni h ≥ log₂(n!). Stirling düsturuna görə log₂(n!) ≈ n log₂ n.
Nəticə: elementləri yalnız bir-biri ilə müqayisə edən istənilən alqoritm ən pis halda `n log n` müqayisə etməlidir. Bu, konkret alqoritmin zəifliyi deyil, məlumat nəzəriyyəsi həddidir.
Bu həddi necə keçmək olar? Müqayisə etməməklə. Əgər elementlərin daxili quruluşundan istifadə edə bilirsənsə:
- Counting sort — dəyərlər məhdud diapazondadırsa (
0..k), sadəcə hər dəyərin neçə dəfə rast gəldiyini sayırsan:O(n + k). 1 milyon istifadəçini yaşa (0-120) görə sıralamaq üçün ideal - Radix sort — rəqəm-rəqəm (və ya bayt-bayt) sıralayır:
O(d × (n + k)). Sabit uzunluqlu açarlar (ID-lər, tarixlər) üçün
Bu alqoritmlərin "həddi keçməsi" hiylə deyil — sadəcə onlar əlavə məlumatdan (dəyər diapazonundan) istifadə edir. Bunu interview-da vurğulamaq güclü siqnaldır.
Praktikada nə istifadə olunur? Bu sual daha faydalıdır, çünki real kodda quicksort-u əl ilə yazmırsan.
- JavaScript —
Array.prototype.sortES2019-dan etibarən stabil olmalıdır. V8 TimSort işlədir: merge sort və insertion sort hibridi, artıq sıralanmış hissələri ("run"ları) tanıyır və real datada çox sürətlidir. Ən vacib tələ: default müqayisə string üzrədir —[10, 9, 1].sort()sənə[1, 10, 9]verir. Ədədlər üçün comparator məcburidir:sort((a, b) => a - b) - Kotlin/JVM — obyektlər üçün
sorted(),sortedBy,sortedWithaltda TimSort çağırır və stabildir. Primitiv massivlərdə (IntArray.sort()) isə dual-pivot quicksort işləyir və stabil deyil — amma primitivlərdə eyni dəyərlər ayırd edilmədiyi üçün bunun praktiki nəticəsi yoxdur - Dart —
List.sort()stabilliyə zəmanət vermir (sənədlərdə açıq yazılıb). Stabillik lazımdırsa,package:collection-dakımergeSortistifadə olunur. Bu, Flutter-də çoxmeyarlı siyahı sıralayarkən real problem olur
Qayda: hazır sort-dan istifadə et. Kitabxana implementasiyaları illərlə optimallaşdırılıb — hibrid yanaşma, kiçik hissələr üçün insertion sort, run tanıma, cache-yönümlü yaddaş nümunələri. Öz quicksort-unu yazmaq üçün əsaslı səbəb lazımdır: qeyri-standart yaddaş məhdudiyyəti, xarici sorting, və ya sorting-in ümumiyyətlə lazım olmaması (məsələn top-K üçün heap kifayətdir).
Interview məsləhəti: "Hansı sorting alqoritmini seçərdin?" sualının düzgün cavabı alqoritmin adı deyil — əvvəlcə sual verməkdir. Dörd sual: datanın ölçüsü nədir? Yaddaş məhdudiyyəti var? Stabillik lazımdır? Data qismən sıralanıbmı? Sonra: "Ümumi halda dilin hazır sort-unu işlədirəm — o, hibriddir və mənim yazacağımdan yaxşıdır. Amma yaddaş kritikdirsə heap sort, stabillik mütləqdirsə merge sort, dəyərlər dar diapazondadırsa counting sort seçərdim." Bu cavab "quicksort, çünki sürətlidir" cavabından qat-qat güclüdür.
📚 Mənbələr və sənədlər
- Array.prototype.sortrəsmideveloper.mozilla.org
Default sıralamanın string müqayisəsi olması və stabillik zəmanəti burada yazılıb.
- Kotlin: sortedrəsmikotlinlang.org