Insertion Sort, yani eklemeli sıralama, diziyi soldan sağa tarar ve her yeni elemanı kendisinden önceki sıralı bölümde uygun yere yerleştirir. Bu işlem, eldeki oyun kartlarını sırayla doğru konuma yerleştirmeye benzer: Yeni elemandan büyük olanlar sağa kaydırılır ve açılan yere yeni eleman konur.
Insertion Sort nasıl çalışır?
Insertion Sort, dizinin solunda giderek büyüyen sıralı bir bölüm oluşturarak çalışır. Başlangıçta ilk eleman tek başına sıralı kabul edilir; sağındaki elemanlar ise henüz işlenmemiştir.
Algoritma sıradaki elemanı anahtar değer olarak alır ve sıralı bölümdeki elemanlarla sağdan sola doğru karşılaştırır. Anahtardan büyük elemanlar birer konum sağa kaydırılır. Daha küçük veya eşit bir elemana ya da dizinin başına ulaşıldığında anahtar, açılan konuma yerleştirilir.
Örneğin elinde soldan sağa 3 ve 7 olarak sıralanmış iki kart olduğunu düşün. Yeni gelen 5 kartını yerleştirmek için 7'yi sağa kaydırıp 5'i 3 ile 7 arasına koyarsın. Böylece elindeki üç kart da sıralı olur.
Karşılaştırma ve adım adım çözüm kurma becerini farklı sorularla sınamak için Algoritmik Düşünme Testi ile pratik yapabilirsin.
Dizi adım adım nasıl sıralanır?
[7, 3, 5, 1, 4] dizisinde önce 7 sıralı bölüm olarak kabul edilir, ardından diğer elemanlar sırayla bu bölüme yerleştirilir. Tablodaki sıralı ve sırasız bölümler, ilgili adım tamamlandıktan sonraki durumu gösterir.
| Adım | Key değeri | Sıralı bölüm | Sırasız bölüm | Kaydırma ve yerleştirme | Dizinin son durumu |
|---|---|---|---|---|---|
| Başlangıç | Henüz seçilmedi | [7] | [3, 5, 1, 4] | İlk eleman sıralı kabul edilir; kaydırma yapılmaz. | [7, 3, 5, 1, 4] |
| 1 | 3 | [3, 7] | [5, 1, 4] | 7 sağa kaydırılır, 3 onun önüne yerleştirilir. | [3, 7, 5, 1, 4] |
| 2 | 5 | [3, 5, 7] | [1, 4] | 7 sağa kaydırılır; 3 yerinde kalır ve 5 araya yerleştirilir. | [3, 5, 7, 1, 4] |
| 3 | 1 | [1, 3, 5, 7] | [4] | 7, 5 ve 3 sağa kaydırılır; 1 başa yerleştirilir. | [1, 3, 5, 7, 4] |
| 4 | 4 | [1, 3, 4, 5, 7] | [] | 7 ve 5 sağa kaydırılır; 3 ve 1 yerinde kalır, 4 araya yerleştirilir. | [1, 3, 4, 5, 7] |
Her adımın sonunda sıralı bölüm bir eleman genişler. Son eleman da yerleştirildiğinde işlenmemiş bölüm kalmaz ve dizinin tamamı küçükten büyüğe sıralanmış olur.
Python ile insertion sort nasıl yazılır?
Python'da insertion sort, her elemanı while döngüsüyle sıralı bölümdeki uygun yerine yerleştirerek uygulanabilir. Aşağıdaki fonksiyon, verilen listeyi yerinde değiştirir ve sıralanmış listeyi döndürür.
def insertion_sort(liste):
for i in range(1, len(liste)):
key = liste[i]
j = i - 1
while j >= 0 and liste[j] > key:
liste[j + 1] = liste[j]
j -= 1
liste[j + 1] = key
return liste
sayilar = [7, 3, 5, 1, 4]
print(insertion_sort(sayilar))Beklenen çıktı:
[1, 3, 4, 5, 7]for döngüsü, ilk eleman tek başına sıralı kabul edildiği için ikinci elemandan başlar. key = liste[i] satırı, yerleştirilecek değeri geçici olarak saklar. Böylece kaydırma sırasında listenin ilgili konumu değişse bile bu değer kaybolmaz.
j = i - 1, sıralı bölümün son elemanını gösterir. while koşulu, hem j indeksinin listenin başını geçmediğini hem de incelenen elemanın key değerinden büyük olduğunu kontrol eder.
Koşul sağlandıkça liste[j + 1] = liste[j] elemanı bir konum sağa kaydırır; j -= 1 ise karşılaştırmayı sola taşır. Döngü sona erdiğinde j + 1, saklanan değerin yerleştirileceği konumdur. Son olarak return liste aynı listeyi döndürür.
Döngüler ve liste işlemleri konusundaki bilgini gözden geçirmek için Python bilgi testini kullanabilirsin.
Zaman karmaşıklığı neden değişir?
Insertion sort'un çalışma süresi, elemanların başlangıçtaki sırasına göre kaç karşılaştırma ve kaydırma gerektiğine bağlıdır. n listedeki eleman sayısını gösterdiğinde, en iyi durum doğrusal, ortalama ve en kötü durum ise karesel büyüme gösterir.
| Durum | Dizinin özelliği | Kaydırma davranışı | Zaman karmaşıklığı |
|---|---|---|---|
| En iyi | Elemanlar zaten artan sıradadır. | Kaydırma yapılmaz. | O(n) |
| Ortalama | Farklı eleman sıralamaları üzerinden değerlendirilir. | Elemanlar gerektiği kadar sola taşınırken aradaki büyük elemanlar sağa kaydırılır. | O(n²) |
| En kötü | Elemanlar ters sıradadır. | Her yeni eleman sıralı bölümün başına yerleştirilir. | O(n²) |
Liste zaten sıralıysa her yeni eleman önceki elemanla karşılaştırılır ve kaydırma gerektirmeden yerinde kalır. Ters sıralı bir listede ise her yeni eleman, önündeki sıralı bölümün tamamından küçük olduğu için bu bölümdeki elemanlar sağa kaydırılır.
Ortalama durum, farklı başlangıç sıralamaları üzerinden yapılan bir değerlendirmedir; tek bir liste için gereken kaydırma sayısı listenin içeriğine bağlıdır. Princeton Üniversitesi algoritma ve veri yapıları özetinde de insertion sort için en iyi durumda doğrusal, ortalama ve en kötü durumda karesel büyüme gösterilir.
Big O gösteriminin nasıl yorumlandığına ilişkin ayrıntılar için sitedeki Big O yazısına da bakabilirsin.
Kararlı sıralama ne anlama gelir?
Kararlı sıralama, sıralama anahtarı eşit olan kayıtların kendi aralarındaki başlangıç sırasının korunmasıdır. Örneğin öğrenci kayıtlarını nota göre sıralarken aynı nota sahip A öğrencisi başlangıçta B öğrencisinden önce geliyorsa, kararlı bir sıralamanın ardından da A, B sırası korunur.
Karşılaştırmanın not üzerinden yapıldığını düşünelim. Başlangıç sırası A (80), C (70), B (80) olan kayıtlar nota göre küçükten büyüğe sıralandığında C (70), A (80), B (80) olur. A ve B'nin notları eşit olduğundan, bu iki öğrencinin birbirine göre sırası değişmez.
Klasik insertion sort uygulamasında liste[j] > key koşulu kullanıldığında, yalnızca yerleştirilecek değerden büyük elemanlar sağa kaydırılır. Eşit değerler kaydırılmadığı için yeni eleman, kendisine eşit olan önceki elemanların arkasına yerleşir. Kayıtlarla çalışırken de aynı ilke, karşılaştırma ilgili anahtar değerleri üzerinden yapıldığında geçerlidir.
Insertion sort, neredeyse sıralı veriler için de pratik bir seçenek olabilir. Elemanlar doğru yerlerinde veya bu yerlere yakınsa, yerleştirme sırasında genellikle daha az kaydırma gerekir. Bunun uygulamadaki etkisi veri düzenine ve kullanılan yönteme bağlıdır.
Hangi uygulama hatalarına dikkat edilmeli?
Insertion sort yazarken sınır kontrolü, yerleştirilecek değerin saklanması ve kaydırma adımının doğru yürütülmesi önemlidir. Aşağıdaki hataları kontrol ederek uygulamanı gözden geçirebilirsin.
Sol sınır kontrolünü atlamak
Kaydırma döngüsünde j >= 0 koşulu bulunmazsa j, dizinin sol sınırının ötesine geçebilir. Python'da negatif indeksler listenin sonundan elemanlara eriştiği için bu durum hemen hata vermeden yanlış karşılaştırmalara da yol açabilir.
Koşulu j >= 0 and liste[j] > key sırasıyla yaz. Böylece Python, indeksin geçerli olduğunu kontrol ettikten sonra liste elemanını karşılaştırır.
Yerleştirilecek değeri saklamamak
Kaydırma işlemine başlamadan önce geçerli elemanı key değişkenine almazsan, üzerine başka bir değer yazıldığında onu kaybedebilirsin. Döngüye girmeden key = liste[i] atamasını yap ve uygun konumu bulduktan sonra bu değeri listeye yerleştir.
Selection sort ile karıştırmak
Insertion sort, sıradaki elemanı soldaki sıralı bölüme yerleştirirken gerekli elemanları kaydırır. Selection sort ise her adımda henüz sıralanmamış bölümden seçilecek elemanı arar ve onu uygun konuma taşır. Bu farkı bilmek, döngülerin hangi amaçla kurulduğunu anlamanı kolaylaştırır.
Uygulamayı kontrol et
- Dış döngü, ikinci elemanı işlemek üzere
1indeksinden başlıyor mu? - Yerleştirilecek eleman, kaydırma başlamadan önce
keydeğişkenine alınıyor mu? whilekoşulunda, listeye erişmeden öncej >= 0kontrol ediliyor mu?- Her kaydırmanın ardından
jbir azaltılıyor mu? - Kaydırma tamamlandığında
key,j + 1konumuna yerleştiriliyor mu?
Sık Sorulan Sorular
Insertion Sort hangi tür dizilerde daha iyi çalışır?
Insertion sort, özellikle küçük veya neredeyse sıralı dizilerde pratik bir seçenek olabilir. Elemanlar doğru konumlarına yakınsa yapılacak kaydırma sayısı azalabilir.
Insertion Sort neden kararlı bir sıralama algoritmasıdır?
Klasik insertion sort, yalnızca yerleştirilecek elemandan büyük olanları kaydırdığı için eşit anahtarlı elemanların birbirine göre sırasını korur. Karşılaştırma koşulunu değiştirmek bu özelliği etkileyebilir.
Insertion Sort ile Selection Sort arasındaki temel fark nedir?
Insertion sort, her yeni elemanı daha önce sıralanmış bölüme yerleştirir; selection sort ise sıralanmamış bölümden uygun elemanı seçerek yerine taşır.
Python'daki insertion_sort(liste) fonksiyonu özgün listeyi değiştirir mi?
Kaydırmaları doğrudan kendisine verilen liste üzerinde yapan insertion_sort(liste) uygulaması özgün listeyi değiştirir. Başlangıçtaki listeyi korumak istersen fonksiyona listenin bir kopyasını verebilirsin.
Kodu kontrol listesiyle karşılaştırıp farklı sıralardaki küçük diziler üzerinde denemek, her elemanın nasıl yerleştirildiğini takip etmene yardımcı olur.
