Insertion Sort
Eklemeli Sıralama
- Okunuşu
- insörşın sort
Kısaca
Insertion sort (eklemeli sıralama), sıralı listeyi öğe öğe kurar; her yeni öğeyi sıralanmışlar arasında yerine koyar, tıpkı eldeki kartları dizmek gibi.
Insertion sort nedir?
Algoritma listenin sol kısmını sıralı tutar. Bir sonraki öğeyi alır, onu sıralı öğelerle sağdan sola karşılaştırır, daha büyük olanları bir konum sağa kaydırır ve yeni öğeyi boşluğa bırakır. Bunu her öğe için tekrarlamak tamamen sıralı bir liste üretir.
En kötü durumda, yani ters sıralı bir listede, her öğe en sola kadar ilerler; bu da O(n²) zaman verir. Ama girdi zaten neredeyse sıralıysa her öğe yalnızca biraz hareket eder ve çalışma süresi O(n)'e yaklaşır. O(1) ek bellekle yerinde sıralar, kararlıdır ve veriyi geldikçe, öğe öğe sıralayabilir.
Küçük ve neredeyse sıralı girdilerdeki bu verimlilik, insertion sort'u gerçek dünyadaki hızlı sıralamaların yapı taşlarından biri yapar. 2002'den beri Python'un sıralama algoritması olan ve Java'nın nesneleri sıralamak için kullandığı Timsort kısa diziler (run) için insertion sort kullanır; birçok C++ standart kütüphanesinde kullanılan introsort uygulamaları da küçük bölümlerde ona geçer.
Sık yapılan bir yanlış, her O(n²) sıralamanın eşit derecede işe yaramaz olduğunu düşünmektir. Insertion sort'un ek yükü düşüktür ve neredeyse sıralı veride mükemmel davranır; birkaç düzine öğelik küçük dizilerde O(n log n) algoritmalarını geride bırakmasının ve en iyi genel amaçlı sıralamaların içinde yaşamaya devam etmesinin nedeni budur.
Önemli noktalar
- Insertion sort her öğeyi sıralı bir ön kısım içinde yerine yerleştirir.
- En kötü durumda O(n²), ama neredeyse sıralı veride O(n)'e yakındır.
- Yerindedir, kararlıdır ve öğeleri geldikçe sıralayabilir.
- Timsort ve introsort onu küçük parçalar için kullanır.
- Küçük dizilerde çoğu zaman O(n log n) algoritmalarını geçer.
Örnek
def insertion_sort(items):
items = list(items)
for i in range(1, len(items)):
current = items[i]
j = i - 1
while j >= 0 and items[j] > current: # shift larger elements right
items[j + 1] = items[j]
j -= 1
items[j + 1] = current # drop the element into the gap
return items
print(insertion_sort([12, 11, 13, 5, 6])) # [5, 6, 11, 12, 13]Sık sorulan sorular
Insertion sort ne zaman iyi bir seçimdir?
Küçük diziler, zaten neredeyse sıralı veriler ya da sıralı tutulması gereken, tek tek gelen öğeler için. Büyük ve rastgele veriler için bir O(n log n) algoritması çok daha hızlıdır.
Insertion sort kararlı mı?
Evet. Yalnızca eklenen öğeden kesinlikle büyük olan öğeleri kaydırır; bu yüzden eşit öğeler göreli ilk sıralarını korur.
Hızlı sıralama algoritmaları neden içeride insertion sort kullanır?
Çünkü küçük alt dizilerde onun basit döngüsü ve düşük ek yükü, böl ve yönet algoritmalarının hesap işlerini geçer. Timsort ve introsort gibi karma sıralamalar bir boyut eşiğinin altında ona geçer.
İlgili sayfalar
- Sıralama AlgoritmasıVeri Yapıları, s. 30Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
- Bubble SortVeri Yapıları, s. 7Bubble sort (kabarcık sıralaması), sırası bozuk komşu öğeleri yer değiştiren basit bir sıralama algoritmasıdır; her geçiş kalan en büyük değeri sona taşır.
- Merge SortVeri Yapıları, s. 26Merge sort, bir listeyi ikiye bölen, her yarıyı özyinelemeyle sıralayan ve sıralı yarıları O(n log n) sürede birleştiren böl ve yönet sıralama algoritmasıdır.
- QuicksortVeri Yapıları, s. 28Quicksort, öğeleri seçilen bir pivot etrafında bölümleyen, sonra küçük ve büyük grupları aynı şekilde sıralayan bir böl ve yönet sıralama algoritmasıdır.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin