Ekleme Sıralaması

Herkese merhaba bu yazımızda sıralama algoritmalarından insertion sort algoritmasına değineceğiz.Bu yazıyı okumadan önce sıralama algoritmalarını adım adım incelemek için buraya tıklayınız ve site üzerinden sıralama algoritmalarını inceleyiniz.

Ekleme sıralaması ilerleyen haftalarda anlatacağımız merge sort ve quicksort algoritmalarına göre yavaş bir algoritmadır ayrıca bu algoritmalara göre hafızayı yormaz fakat işlem maliyetini artırıcı kodlama stilleri vardır.Genellikle algoritmayı while kullanarak döngüye sokan stiller ile kodlanır bu da algoritmanın kod maliyetini artırıcı bir unsurdur.

Örnek olarak 8, 6, 7, 2, 3, 4, 5, 1 dizisini ele alalım.Burada dizinin ilk elemanı olan 8 sayısından başlayarak diziyi sıralı hale getirmeye çalışalım.

İlk adımda;(pass) sadece 8 sayısı sıralanmış olur.Bu durumda tek sayı olduğu için herhangi bir işlem yapılmaz.

8 | 6, 7, 2, 3, 4, 5, 1 (| işareti sıralanan sayıları belirtir.Bu işaretin solundaki kısımlar sıralanmıştır.Biz her adımda | işaretinin soluna eleman ekleyerek sıralarız)

Ikinci adımda 8 ve 6 sayılarını ele alarak bu sayıları sıralı biçimde diziye atarız.Bu adımda 2 sayıyı sıralamak için başka bir algoritma kullanılabilir.

8 6 | 7, 2, 3, 4, 5, 1 1.Adım_1

6 8 | 7, 2, 3, 4, 5, 1 1.Adım_2

6 8 7 | 2, 3, 4, 5, 1 2.Adım_1

6 7 8 | 2, 3, 4, 5, 1 2.Adım_2

6 7 8 2 | 3, 4, 5, 1 3.Adım_1

2 6 7 8 | 3, 4, 5, 1 3.Adım_2

2 3 6 7 8 | 4, 5, 1 4.Adım_1 diye devam ederek en sonunda dizimizi sıralı hale getirmiş oluruz. Yukarıdaki görselde adım adım dizinin sıralanış biçimini görüyoruz.

Algoritmanın Karmaşıklığı

Ekleme algoritmasının;

• Worst case değeri dizi tam ters sıralı biçimde verilirse dikkate alınır.Bu değer her sayı için n kadar dolaşacağı için n(n+1) / 2 ⇒ big O(n^2) şeklinde karmaşıklığı verilir.
• Best case değeri ise algoritmanın tam sıralı biçimde verilmesi ile elde edilir.Bu durumda herhangi bir işlem yapılamayacağı için n sayı için best case n olarak tanımlanır.
• Bu iki karmaşıklık değerinin ortalaması olan mid-case değeri ise n^2 olarak bulunur.

Bu algoritmayı kendi sayılarınız ile test etmek için buraya tıklayınız.

Son

Buraya kadar okuduğunuz için teşekkürler.Umarım faydalı bir yazı olmuştur.Herkese sağlıklı günler.