Bölüm 9 · Yazılımın içi · Ders 39

Sıralama algoritmaları

Ekleme, birleştirme ve taban sıralaması aynı sonar okumalarında

Veri. Robotun önündeki sonar, bir tarama boyunca 24 mesafe okuması (20–399 cm) verdi. Ortanca mesafeyi ve en yakın 3 engeli bulmak için okumaları sıralamak gerekiyor. Aynı diziyi üç farklı algoritmayla sıralayıp kaç karşılaştırma ve kaç yazma yaptıklarını sayıyoruz.

24 sonar okuması (cm), karışık sırada24 okuma · ekleme sıralaması

1 / 176

Algoritma (0 ekleme · 1 birleştirme · 2 taban) 0Dizi boyu 24

siralama.pypython

import numpy as np
rng = np.random.default_rng(5)
a, c = [int(v) for v in rng.integers(20, 400, 24)], [0, 0] # sonar (cm), sayaçlar
def insertion(a):
for i in range(1, len(a)): # a[:i] hep sıralı
for j in range(i, 0, -1):
c[0] += 1 # karşılaştırma
if a[j - 1] <= a[j]: break # yerine oturdu
a[j - 1], a[j] = a[j], a[j - 1] # sola kaydır
return a
def merge(a):
if len(a) < 2: return a
h = len(a) // 2
L, R, out = merge(a[:h]), merge(a[h:]), [] # iki yarıyı sırala
while L and R:
c[1] += 1 # önleri karşılaştır
out.append((L if L[0] <= R[0] else R).pop(0)) # küçüğü al
return out + L + R # artanları ekle
def radix(a):
for d in (1, 10, 100): # birler, onlar, yüzler
a = [v for k in range(10) for v in a if v//d%10==k] # kova k, sıra korunur
return a
print(insertion(a[:]) == merge(a) == radix(a) == sorted(a))
print("ekleme, birleştirme:", c) # karşılaştırma sayıları

Sahnedeki her sayı, aynı algoritmanın tarayıcında yapılan gerçek çalıştırmasından gelir (sabit tohum, her seferinde aynı sonuç). Python kodunu kendi bilgisayarında çalıştırırsan rastgele başlangıçlar farklı olacağı için sayılar biraz değişebilir.

Veri seti

Tüm veri setleri →

Bu dersin kodu verisini kendi içinde üretir; indirilecek dosya yok. Kodu yine de aşağıda tarayıcında çalıştırabilirsin.

Kodu tarayıcıda çalıştırPython · NumPy · matplotlib · Pyodide

Python ve NumPy bu sayfada, tarayıcında çalışır (Pyodide). Kodu değiştirip yeniden çalıştırabilirsin; dersin veri setleri çalışma klasöründe hazır. Kod matplotlib kullanırsa grafikler çıktının altında görünür, yazdığı dosyalar (ör. egitim_gecmisi.csv) indirilebilir.

siralama.pypython

import numpy as np
rng = np.random.default_rng(5)
a, c = [int(v) for v in rng.integers(20, 400, 24)], [0, 0]  # sonar (cm), sayaçlar
def insertion(a):
    for i in range(1, len(a)):                # a[:i] hep sıralı
        for j in range(i, 0, -1):
            c[0] += 1                         # karşılaştırma
            if a[j - 1] <= a[j]: break        # yerine oturdu
            a[j - 1], a[j] = a[j], a[j - 1]   # sola kaydır
    return a
def merge(a):
    if len(a) < 2: return a
    h = len(a) // 2
    L, R, out = merge(a[:h]), merge(a[h:]), []  # iki yarıyı sırala
    while L and R:
        c[1] += 1                             # önleri karşılaştır
        out.append((L if L[0] <= R[0] else R).pop(0))  # küçüğü al
    return out + L + R                        # artanları ekle
def radix(a):
    for d in (1, 10, 100):                    # birler, onlar, yüzler
        a = [v for k in range(10) for v in a if v//d%10==k]  # kova k, sıra korunur
    return a
print(insertion(a[:]) == merge(a) == radix(a) == sorted(a))
print("ekleme, birleştirme:", c)              # karşılaştırma sayıları

Kendi CSV’ni yükle

Çıktı

Çıktı burada görünecek.

Nasıl çalışır

Ekleme: soldaki kısım hep sıralıdır; yeni eleman, kendinden büyük komşusuyla yer değiştirerek yerine kayar. Rastgele dizide yaklaşık n²/4 karşılaştırma; neredeyse sıralı dizide yaklaşık n.
Birleştirme: diziyi ikiye böl, her yarıyı sırala, iki sıralı yarıyı baştan karşılaştırarak birleştir. Her düzeyde en çok n karşılaştırma, log2 n düzey: ~n log2 n.
LSD taban: hiç karşılaştırmaz. Önce birler basamağına, sonra onlar, sonra yüzler basamağına göre kararlı biçimde kovalara dağıtır; 3 geçişte biter (n + aralık işi).
Timsort (Python'un sorted'ı) gerçek veride hazır gelen artan parçaları bulur, kısa parçaları eklemeyle uzatır ve parçaları birleştirmeyle birleştirir: sıralı veride n, en kötü durumda n log n.
Şunu dene: dizi boyunu 12’den 48’e çıkar; ekleme sayacı ~16 kat, birleştirme ~7 kat büyür, taban yalnız 4 kat.

Neden önemli

Sıralama, ortanca süzgeç (sensör gürültüsünü bastırmak), en yakın engelleri seçme, olayları zaman damgasına göre dizme ve ikili aramaya hazırlık için her gün çalışır. Mikrodenetleyicide küçük dizilerde ekleme sıralaması çoğu zaman en hızlısıdır; büyük ve tam sayı verilerde taban sıralaması, genel amaçlı işte ise Timsort ya da birleştirme tercih edilir.

ESOF 323, 11. hafta: robotlarda derin öğrenme →