Algoritma ve Programlama Dünyası — Uygulama 4 (Insertion Sort)

Merhaba sevgili okurlar! Algoritma ve programlama dünyası serisinin bir önceki bölümünde, ‘Python ile Recursion Uygulaması’ yapmıştık. Eğer önceki yazıyı okumadıysanız, bu linke tıklayarak ulaşabilirsiniz. Bu bölümde, “Insertion Sort” adı verilen bir sıralama algoritması üzerinde duracağız ve Python dilinde bu algoritmanın nasıl uygulanacağını göstereceğiz.

Insertion Sort Nedir?

Insertion Sort, bir sıralama algoritmasıdır. İsmini, sıralanacak listeyi sanki elinizdeki bir deste kartı sıralıyormuş gibi ele almasından alır. Her adımda, sıralanacak bir sonraki elemanı alır ve bu elemanı, sıralanmış listeye doğru konumuna “yerleştirir”. Bu işlem, tüm liste sıralanana kadar devam eder.

Photo by Dan Burton on Unsplash

Python’da Insertion Sort Uygulaması

Python dilinde Insertion Sort algoritmasının uygulaması aşağıdaki gibidir:

def insertion_sort(liste):
    for i in range(1, len(liste)):
        anahtar = liste[i]
        j = i-1
        while j >=0 and anahtar < liste[j] :
                liste[j+1] = liste[j]
                j -= 1
        liste[j+1] = anahtar

Bu kodda, `i` döngü değişkeni sıralanacak olan sonraki elemanın indeksini tutar. `Anahtar` değişkeni ise sıralanacak olan sonraki elemanın değerini tutar. `j` değişkeni, sıralanmış listeyi tarar ve `anahtar` değerinin yerleştirileceği konumu bulur.

Şimdi bu algoritmayı bir örnekle görelim. Aşağıdaki kodu çalıştırdığımızda:

liste = [8, 5, 2, 9, 5, 6, 3]
insertion_sort(liste)
print(liste)

Çıktı olarak sıralanmış listeyi alırız:

[2, 3, 5, 5, 6, 8, 9]

Bu, Insertion Sort algoritmasının doğru bir şekilde çalıştığını gösterir. Algoritma, verilen listeyi küçükten büyüğe doğru sıraladı.

Algoritmanın Görsel Örneği

Bu bölümde, Insertion Sort algoritmasının bir dizi üzerindeki değişiminin görsel örneğini sunacağım. Bu örnekte, `[8, 5, 2, 9, 5, 6, 3]` dizisini sıralayacağız.

İlk adım: [8 | 5 2 9 5 6 3]
İkinci adım: [5 8 | 2 9 5 6 3]
Üçüncü adım: [2 5 8 | 9 5 6 3]
Dördüncü adım: [2 5 8 9 | 5 6 3]
Beşinci adım: [2 5 5 8 9 | 6 3]
Altıncı adım: [2 5 5 6 8 9 | 3]
Yedinci adım: [2 3 5 5 6 8 9 |]

Bu örnekte, her adımda “|” işareti, sıralanmış kısmı ve sıralanmamış kısmı ayırır. Her adımda, sıralanmamış kısmın ilk elemanı, sıralanmış kısmın uygun yerine eklenir. Bu işlem, sıralanmamış kısım boş kalana kadar devam eder.

Algoritmanın Zaman ve Hafıza Karmaşıklığı

Kısaca, insertion Sort algoritmasının zaman karmaşıklığı, en kötü durumda O(n²), en iyi durumda ise O(n)’dir. Hafıza karmaşıklığı ise O(1)’dir, çünkü ekstra bir hafıza alanı kullanmaz.

Zaman Karmaşıklığı:

• En İyi Durum: En iyi durum, girdi dizisinin zaten sıralı olduğu durumdur. Bu durumda, Insertion Sort her elemanı bir önceki elemanla karşılaştırır ve her elemanın zaten doğru konumda olduğunu görür. Bu durumda, algoritma lineer zaman karmaşıklığına sahip olur, yani O(n).
• En Kötü Durum: En kötü durum, girdi dizisinin tamamen ters sıralı olduğu durumdur. Bu durumda, her yeni elemanın sıralı alt dizide doğru konuma yerleştirilmesi için tüm alt dizi boyunca geçilmesi gerekecektir. Bu durumda, algoritma karesel zaman karmaşıklığına sahip olur, yani O(n²).
• Ortalama Durum: Ortalama durumda da algoritma O(n²) zaman karmaşıklığına sahip olur. Çünkü her elemanın doğru konuma yerleştirilmesi için genellikle mevcut sıralı alt dizi boyunca bir dizi geçişi gereklidir.

Hafıza Karmaşıklığı:

Insertion Sort, yerinde bir sıralama algoritmasıdır, yani ekstra bir hafıza alanı gerektirmez. Sadece birkaç değişken için sabit miktarda hafıza gerektirir (örneğin, geçici bir değişken ve döngü indeksleri). Bu nedenle, hafıza karmaşıklığı O(1)’dir, yani sabittir.

Bu özellikler, Insertion Sort’un küçük diziler için oldukça etkili olmasını sağlar. Ancak, dizi boyutu büyüdükçe, karesel zaman karmaşıklığı nedeniyle performansı düşer. Bu nedenle, büyük diziler için genellikle daha verimli algoritmalar tercih edilir.

Sonuç

Bu bölümde, Insertion Sort adlı bir sıralama algoritmasını ve bu algoritmanın Python dilinde nasıl uygulanacağını gördük. Algoritmanın zaman ve hafıza karmaşıklığı hakkında bilgi verdik ve bir dizi üzerindeki değişiminin görsel bir örneğini sunduk. Umarım bu bilgiler sizin için faydalı olmuştur. Bir sonraki bölümde görüşmek üzere!

Eğer bu yazıyı beğendiyseniz aşağıdaki alkışa istediğiniz kadar tıklayarak yazılarıma destek olabilirsiniz :)

Herhangi bir sorunuz olursa veya benimle iletişim kurmak isterseniz, tüm sosyal medya hesaplarım aşağıdaki linkte yer alıyor.

Turhan Can Kargin | Home

Ayrıca diğer blog yazılarımı aşağıda yer alan websitem üzerinden takip edebilirsiniz.

Turhan Can Kargın

Bir sonraki yazıda görüşmek üzere!