Sürətli çeşidləmə

9.1 Sürətli sıralamanın tərifi

Sürətli Sıralama (Quick Sort) — bu effektiv bir sıralama alqoritmidir ki, "böl və idarə et" yanaşmasından istifadə edir. O, pivot (dayaq elementi) seçərək, array-i iki alt array-ə bölərək işləyir — pivotdan kiçik elementlər və pivotdan böyük elementlər, sonra isə həmin prosesi hər bir alt array-ə rekursiv olaraq tətbiq edir.

Sürətli sıralama alqoritmi, "balaca elementləri sola, böyük elementləri sağa necə daha sürətli atmaq olar?" problemini həll etmək cəhdi kimi ortaya çıxıb. Tutaq ki, ən kiçik element sağdadır. Necə edək ki, onu birbaşa final mövqeyinə olmasa da, ən azından ona yaxın bir yerə köçürək? Bu, çox lazımsız müqayisələrin sayını xeyli azalda bilərdi.

İş prinsipi:

1. Pivot element seçimi:

Array-dən pivot (dayaq element) olaraq bir element seçirik. Bu, birinci element, sonuncu element, orta element, ya da təsadüfi bir element ola bilər. Bəzən üç təsadüfi elementin ədədi orta göstəricisi istifadə olunur.

2. Bölünmə (partitioning):

Pivotdan kiçik olan bütün elementləri array-in sol hissəsinə, böyük olanları isə sağ hissəsinə yerləşdiririk. Nəticədə pivot element array-in sıralanmış vəziyyətdəki son mövqeyində yerləşir.

3. Rekursiv tətbiq:

Prosesi sol və sağ alt array-lərə pivot element daxil etmədən rekursiv olaraq tətbiq edirik.

Addım-addım proses

1. Pivot element seçirik.
2. Pivotdan kiçik elementləri sola, böyük elementləri isə sağa yerləşdiririk.
3. Prosesi alt array-lərə rekursiv olaraq tətbiq edirik.

Sürətli sıralamanın vaxt və yaddaşa görə mürəkkəblik dərəcəsi

Zaman mürəkkəbliyi:

• Ən pis halda: O(n^2) — hər dəfə ən pis pivot element seçildikdə olur (məsələn, array artıq sıralanmış olduqda).
• Orta halda: O(n log n) — təsadüfi paylanmış məlumatlar üçün.
• Ən yaxşı halda: O(n log n) — array hər dəfə bərabər hissələrə bölündükdə.

Yaddaş mürəkkəbliyi:

O(log n) — rekursiya çağırışlarının stekinin saxlanılması üçün lazım olur, əgər tail recursion istifadə olunursa və pivot elementlər uğurla seçilirsə.

9.2 Sürətli çeşidləmə alqoritminin tətbiqi

Python-da tətbiqi:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Əsas hal: 0 və ya 1 elementi olan massiv artıq çeşidlənib
    
    pivot = arr[len(arr) // 2]  # Dayaq elementi seçirik
    left = [x for x in arr if x < pivot]  # Dayaq elementdən kiçik olan elementlər
    middle = [x for x in arr if x == pivot]  # Dayaq elementə bərabər olan elementlər
    right = [x for x in arr if x > pivot]  # Dayaq elementdən böyük olan elementlər
    
    return quick_sort(left) + middle + quick_sort(right)

# İstifadə nümunəsi:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Çeşidlənmiş massiv:", sorted_arr)
# Çıxış: Çeşidlənmiş massiv: [1, 1, 2, 3, 6, 8, 10]

Alqoritmin iş nümunəsi

Massiv nümunəsi götürək: [3, 6, 8, 10, 1, 2, 1]

Birinci keçid:

• Dayaq element: 8
• Sol elementlər: [3, 6, 1, 2, 1]
• Orta elementlər: [8]
• Sağ elementlər: [10]

Sol hissənin rekursiv çeşidlənməsi [3, 6, 1, 2, 1]:

• Dayaq element: 1
• Sol elementlər: []
• Orta elementlər: [1, 1]
• Sağ elementlər: [3, 6, 2]

Sağ hissənin rekursiv çeşidlənməsi [3, 6, 2]:

• Dayaq element: 6
• Sol elementlər: [3, 2]
• Orta elementlər: [6]
• Sağ elementlər: []

Sol hissənin rekursiv çeşidlənməsi [3, 2]:

• Dayaq element: 2
• Sol elementlər: []
• Orta elementlər: [2]
• Sağ elementlər: [3]

Birləşmə nəticəsi belə olacaq: sol hissə üçün [1, 1, 2, 3, 6], sağ hissə üçün [10] və orta üçün isə [8].

Son çeşidlənmiş massiv: [1, 1, 2, 3, 6, 8, 10]