1 dk, tahmini okuma süresi
Python İle Ekleme Sıralama
En Son Güncelleme: 23 Eylül, 2022Ekleme sıralama, nispeten daha küçük listelerde (veya dizilerde) çok iyi çalışabilen basit sıralama algoritmalarından biridir. İkinci bir yineleme başlatması gerekmediği, zaten kısmen sıralanmış dizilerde daha iyi performans gösterir. Nedenini hemen göreceğiz.
Tamam, temelde iki bitişik değeri karşılaştırıyoruz ve eğer yanlış sıradalarsa onları değiştiriyoruz. Bu, mevcut en düşük değeri listenin başına taşımamıza yardımcı olacaktır (maksimum sıralamada).
§Anlamamıza Yardımcı Olacak Bir Liste
İlk yinelememiz dizi/liste boyutu eksi bir çalıştıracağız. İkinci döngümüz, mevcut değerin bitişik değerle değiştirilmesi gerektiğinde tetiklenir. İkinci döngünün bir sonraki uygulamasında değiştirme gerekliyse, bir öncekinden bir indeks kalan değerlerde tekrar takas ihtiyacını ararız. Bu şekilde her yinelemede en düşük değeri öne iteriz. Bu mantık, oyun kartlarını elimizde nasıl sıralayacağımıza yakın değil mi?
def insertionsort(arr, size):
for i in range(1, size):
j = i-1
while j>=0 and arr[i] < arr[j]:
arr[j], arr[i] = arr[i], arr[j]
j -= 1
i -= 1
array = [5,4,6,8,2,7,1]
sz = len(array)
insertionsort(array, sz)
print(array)
Bu örnek üzerinde adım adım ilerlemenin bize çok yardımcı olacağını düşünüyorum.
İkinci döngü başladığında i=1 ve j=0 ile başlıyoruz. Ardından dizinin sınırları içinde olup olmadığımızı kontrol ederiz. Eğer öyleyse while döngüsünü başlatıyoruz. dizi[i], dizi[j]'den küçükse (sol sağdan büyükse), bir dizin solundaki iki değeri kontrol etmek için i ve j'yi değiştirir ve birer birer azaltırız. Böylece, ikinci döngünün ilk yinelemesinin sonunda dizimiz şöyle görünür:
[4, 5, 6, 8, 2, 7, 1]
Gördüğünüz gibi 4 ve 5 yerlerini değiştirdik ve solda hiçbir değerimiz olmadığı için duruyoruz. İlk yinelemenin ikinci uygulamasına i=2 ve j=1 ile başlıyoruz. Değiştirmeye gerek yok, bu yüzden devam ediyoruz. Üçüncü uygulamada da değiştirme yapmaya gerek yok.
İlk yinelemenin dördüncü uygulamasında j=3 ve i=4. İlk takastan sonra (2 ve 8) :
[4, 5, 6, 2, 8, 7, 1]
Şimdi i ve j'yi birer azaltıp tekrar kontrol ediyoruz. Başka bir takas gerekli ve sonuç (6 ve 2 takas edildi):
[4, 5, 2, 6, 8, 7, 1]
Bunun mantığını anladığınızı varsayıyorum, bu yüzden her adımı şu şekilde açıklamaya gitmiyoruz. Bu yazıyı olması gerekenden çok daha uzun yapar. Dizimizin ilk değeri 2 olana kadar while döngüsünü çalıştırmaya devam ediyoruz. Sıralanmış bir dizimiz olana kadar en düşük olanı "seçmeye" ve öne doğru itmeye devam edeceğiz.
§Seçim Sıralamasının Karmaşıklığı
Seçim sıralama, O(N²) zaman karmaşıklığına sahip. Bir yineleme içinde iç içe geçmiş bir döngü ile zaman açısından çok verimli değildir. Ancak değerlerimizi veya herhangi bir şeyi korumak için ağır bir yardımcı dizi tutmamız gerekmediği için yer aşısından gerçekten verimli. Seçim sıralamasının yer karmaşıklığı O(1)'dir. Bu yüzden bir dahaki sefere zamanınız olduğunda ama yeriniz olmadığında bu algortimayı düşünebilirsiniz.
Öğrenmeye devam edin!
Ilker AkbiyikBenzer Paylaşımlar
