Çeşidləmə alqoritmləri

Telefonundakı kontaktlar əlifba sırası ilə, oyundakı reytinq cədvəli xallara görə, onlayn mağazada məhsullar isə qiymətə görə düzülür. Bütün bu hallarda kompüter çeşidləmə (nizamlama) aparır — elementləri müəyyən qaydaya görə sıraya düzür. Üstəlik, əvvəlki dərsdə gördük ki, sürətli ikili axtarış yalnız nizamlanmış siyahıda işləyir. Bəs kompüter siyahını necə nizamlayır?

Qabarcıq üsulu

Qabarcıq üsulunda qonşu elementlər cüt-cüt müqayisə olunur: soldakı sağdakından böyükdürsə, onların yeri dəyişdirilir. Siyahının bir dəfə başdan-başa yoxlanmasına keçid deyilir. Hər keçiddən sonra qalan elementlərin ən böyüyü suyun içindəki qabarcıq kimi «üzə çıxır» — siyahının sonuna gedir. Hansısa keçiddə heç bir yerdəyişmə olmasa, siyahı artıq nizamlanıb.

def bubble_sort(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

print(bubble_sort([5, 1, 4, 2]))
print(sorted(['Murad', 'Aysel', 'Leyla', 'Elvin']))

[1, 2, 4, 5]
['Aysel', 'Elvin', 'Leyla', 'Murad']

Seçmə üsulu

Seçmə üsulunda siyahının nizamlanmamış hissəsində ən kiçik element tapılır və həmin hissənin birinci elementi ilə yeri dəyişdirilir. Beləliklə, soldakı nizamlanmış hissə hər addımda bir element böyüyür.

Daxiletmə üsulu

Daxiletmə üsulu kart oyunçusunun əlindəki kartları düzməsinə bənzəyir: o, növbəti kartı götürür və onu artıq düzülmüş kartlar arasında öz yerinə «daxil edir». Siyahı demək olar ki, nizamlanmış olanda bu üsul çox sürətli işləyir.

Hansı alqoritm daha sürətlidir?

Çeşidləmənin sürəti adətən müqayisələrin sayı ilə ölçülür. Üç sadə üsulun hər biri ən pis halda təxminən n(n − 1) / 2 müqayisə aparır: n = 10 üçün 45, n = 1000 üçün isə 499 500. Siyahı 10 dəfə uzananda iş təxminən 100 dəfə artır!