10.1 Müxtəlif sıralama alqoritmlərinin müqayisəsi
Budur müxtəlif sıralama alqoritmləri üçün müqayisə cədvəli:
| Alqoritm | Ən yaxşı vaxt | Orta vaxt | Ən pis vaxt | Məkan mürəkkəbliyi | Sabitlik |
|---|---|---|---|---|---|
| Bubble Sort (Baloncuk Sıralama) | O(n) | O(n^2) | O(n^2) | O(1) | Bəli |
| Insertion Sort (Daxiletmə Sıralama) | O(n) | O(n^2) | O(n^2) | O(1) | Bəli |
| Selection Sort (Seçim Sıralama) | O(n^2) | O(n^2) | O(n^2) | O(1) | Xeyr |
| Heap Sort (Yığın Sıralama) | O(n log n) | O(n log n) | O(n log n) | O(1) | <span class="text-warning>Xeyr |
10.2 Müxtəlif tapşırıqlar üçün sıralama alqoritminin seçilməsi meyarları
Hər bir alqoritmin güclü və zəif tərəfləri var. Kiçik məlumat həcmində hətta Bubble Sort ən yaxşı seçim ola bilər.
Sən bu meyarlara diqqət yetirməlisən:
1. Məlumatların həcmi:
- Kiçik məlumat cədvəlləri (n < 1000):
- Bubble Sort, Insertion Sort: sadə və anlaşılan, kiçik məlumat cədvəlləri üçün effektivdir.
- Böyük məlumat cədvəlləri (n > 1000):
- Merge Sort, Quick Sort, Heap Sort: daha mürəkkəb, amma böyük məlumat həcmləri üçün effektivdir.
2. Məlumat strukturu:
- Demək olar ki sıralanmış məlumatlar:
- Insertion Sort: demək olar ki sıralanmış məlumatlar üçün demək olar ki xətti işləyir.
- Təsadüfi məlumatlar:
- Quick Sort, Merge Sort, Heap Sort: təsadüfi məlumatlar üçün effektivdir.
3. Stabilik:
- Stabil sıralama tələb olunur:
- Insertion Sort, Merge Sort: eyni dəyərlərə malik elementlərin nisbi sırasını saxlayır.
- Stabil sıralama tələb olunmur:
- Selection Sort, Quick Sort, Heap Sort: stabilik vacib olmadığı halda istifadəsi mümkündür.
4. Əlavə yaddaş:
- Məhdud yaddaş:
- Insertion Sort, Selection Sort, Heap Sort: əlavə yaddaş kimi
O(1)istifadə edir.
- Insertion Sort, Selection Sort, Heap Sort: əlavə yaddaş kimi
- Əlavə yaddaş mövcuddur:
- Merge Sort:
O(n)əlavə yaddaş tələb edir, amma böyük məlumatlar üçün effektiv ola bilər.
- Merge Sort:
10.3 Bir alqoritmin digərindən üstün olduğu məsələlərə nümunələr
Gəlin indi alqoritmlərdən yox, məsələlərdən başlayaq. Bir alqoritmin digərindən üstün olduğu məsələlərə nümunələr:
1. Kiçik massivlərin sıralanması:
Bubble sort (Kabarcıq sıralama), Insertion sort (Daxil etmə sıralama): Sadə həyata keçirilməsi onları kiçik massivlər üçün, xüsusilə də massivlər artıq demək olar sıralıdırsa, ideal edir.
2. Böyük massivlərin sıralanması:
Quick sort (Sürətli sıralama), Merge sort (Birləşdirmə sıralama), Heap sort (Küçə sıralama): Məlumatların böyük miqdarı üçün logaritmik vaxt mürəkkəbliyi səbəbindən effektivdirlər.
3. Demək olar sıralanmış massivlərin sıralanması:
Məsələn, artıq sıralanmış massivə bir neçə element əlavə etdiniz.
Insertion sort (Daxil etmə sıralama): Belə massivlərdə demək olar lineer işləyir.
4. Sabitlik vacib olan məlumatların sıralanması:
Merge sort (Birləşdirmə sıralama): Eyni elementlərin ardıcıllığını saxlayır və böyük məlumat miqdarları üçün effektivdir.
Insertion sort (Daxil etmə sıralama): Həmçinin ardıcıllığı saxlayır və kiçik məlumat miqdarları üçün effektivdir.
5. Məhdud yaddaş ilə sıralama:
Selection sort (Seçim sıralama), Heap sort (Küçə sıralama): Yalnız O(1) əlavə yaddaş istifadə edir və yaddaş məhduddursa, istifadə edilə bilər.
6. Paralel sıralama:
Merge sort (Birləşdirmə sıralama): Asanlıqla paralelləşdirilə bilər, çünki hər yarını müstəqil sıralamaq olar.
GO TO FULL VERSION