Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise İnsertion Sort algoritmasını anlatmaya çalışacağız.
Bir önceki yazımda sıralamanın ne olduğundan ve sıralama algoritmaları arasındaki farklardan bahsettiğim için bu yazıda direkt olarak algoritmaya ve çalışma mantığına geçmek istiyorum.
İsteyenler bu linkten bir önceki yazıma ulaşabilirler.
İnsertion Sort Nedir?
Türkçe ismi Sokma Sıralaması olan İnsertion Sort algoritması diğer sıralama algoritmalarına nazaran kodlaması oldukça kolaydır. Kodlanması kolay olduğu gibi uygulanması da kolaydır. Genelde kart oyunlarında insanlar elindeki kartları sıralamak için farkında olmadan bu algoritmayı uygulamaktadır. Ancak karmaşıklığı N^2 olduğu için verimli bir algoritma sayılmaz.
İnsertion Sort Nasıl Çalışır?
Algoritmada döngümüz her bir tur döndüğünde sıradaki elemanı sondan başa doğru karşılaştırarak yerine yerleştirme esaslı çalışmaktadır.
Kaba kodu verdikten sonra açıklamaya devam edelim:
for (i = 1; i < n; i++)
{
deger = arr[i];
j = i-1;
while (j >= 0 && arr[j] > deger)
{
arr[j+1] = arr[j];
j–;
}
arr[j+1] = deger;
}
|
for (i = 1; i < n; i++) { deger = arr[i]; j = i–1; while (j >= 0 && arr[j] > deger) { arr[j+1] = arr[j]; j—; } arr[j+1] = deger; } |
Az önce de dediğim gibi üstteki for döngüsü her bittiğinde dizideki i. elemanı yani ‘deger‘ değişkeni doğru yerini bulmuştur. Doğru derken kastettiğim 0 ile i arasındaki doğru yerini bulmuştur. Döngü en sona geldiğinde 0 dan n-1 e kadar herkes doğru yerini bulduğu için dizi sıralanmıştır.
Hemen bir örnek vererek daha rahat kavramaya çalışalım.
Not: ‘[‘ ve ‘]’ ayraçlarıyla ayrılmış kısım halihazırda sıralanmış aralığı temsil eder.
Başlangıç
[10] 3 9 2 1
1. Adım
[3 10] 9 2 1
2. Adım
[3 9 10] 2 1
3. Adım
[2 3 9 10] 1
4. Adım
[1 2 3 9 10]
Karmaşıklık Hesabı
Gördüğünüz üzere her adımda yeni bir eleman sıralanmış kısıma dahil olmaktadır. Karmaşıklık hesabı yaparsak her adımda bütün elemanları gezdiği için en kötü ihtimalde O(N^2)‘dir. Bu algoritma için en iyi ihtimalle başlangıçta dizinin sıralı olmasıdır. Böylelikle hiç yer değiştirme yapmadan sıralama bitecektir.
En kötü durum ise tersten yani bu örnek için büyükten küçüğe sıralanmış bir diziyi girdi olarak vermektir. Her eleman için en başa kadar karşılaştırma yapacağı için yaklaşık N^2 işlem gerçekleşecektir.
Bazı Popüler dillerde İnsertion Sort kodu:
C/C++
void insertionSort(int arr[], int n)
{
int i, deger, j;
for (i = 1; i < n; i++)
{
deger = arr[i];
j = i-1;
while (j >= 0 && arr[j] > deger)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = deger;
}
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void insertionSort(int arr[], int n) { int i, deger, j; for (i = 1; i < n; i++) { deger = arr[i]; j = i–1;
while (j >= 0 && arr[j] > deger) { arr[j+1] = arr[j]; j = j–1; } arr[j+1] = deger; } } |
Java
void sort(int arr[])
{
int n = arr.length;
for (int i=1; i
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = deger;
}
}
|
void sort(int arr[]) { int n = arr.length; for (int i=1; i<n; ++i) { int deger = arr[i]; int j = i–1; while (j>=0 && arr[j] > deger) { arr[j+1] = arr[j]; j = j–1; } arr[j+1] = deger; } } |
Python
def insertionSort(arr):
for i in range(1, len(arr)):
deger = arr[i]
j = i-1
while j >=0 and deger< arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = deger
|
def insertionSort(arr):
for i in range(1, len(arr)): deger = arr[i]
j = i–1 while j >=0 and deger< arr[j] : arr[j+1] = arr[j] j -= 1 arr[j+1] = deger |
Okuduğunuz için teşekkürler umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.
Tüm Algoritma Derslerimiz İçin tıklayınız.
71