Bubble, selection ve insertion sort

Bubble sort komşu terslikleri swap ederek büyük öğeyi sona taşır. Bir turda swap olmadıysa bitirme kontrolü sıralı girdiyi doğrusal yapar. Selection sort kalan en küçüğü seçip başa koyar; karşılaştırma sayısı girdi sıralı olsa da kareseldir. Insertion sort öğeyi sıralı prefix'e doğru yere yerleştirir; az inversiyonlu veride etkilidir.

Stability, eşit anahtarlı kayıtların eski göreli sırasının korunmasıdır. Insertion'da yalnız büyük elemanları kaydırırsan stabil kalır; eşitleri de kaydırmak sırayı bozabilir. Selection'ın standart uzak swap uygulaması stabil değildir. In-place sözü çoğu zaman O(1) yardımcı alanı anlatır; recursive stack'i ayrıca say.

Bu yöntemler yalnız oyuncak değildir: küçük parçaları insertion ile bitiren hibrit sıralamalar vardır. Ama milyon kayıt için karesel algoritmayı “kodu kısa” diye seçme. Aynı veride comparator tutarsızsa hiçbir sıralama sözleşmesi kurtarmaz; total order, NaN ve locale karşılaştırması ayrı mühendislik kararlarıdır.

def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        x, j = a[i], i-1
        while j >= 0 and a[j] > x:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = x
    return a
assert insertion_sort([4,2,3]) == [2,3,4]