Ekleme Sıralama Algoritması Açıklaması

Ekleme Sıralama (Insertion Sort), sıralı bir diziyi birer birer öğe ekleyerek oluşturan, basit, karşılaştırma tabanlı bir sıralama algoritmasıdır. Dizinin sıralı olmayan kısmından her elemanı alıp, sıralı kısmın içine doğru konumuna yerleştirerek çalışır.

Ekleme Sıralama'nın anlaşılması ve uygulanması kolaydır ve sıralama algoritmalarının nasıl çalıştığını öğrenmek için çok faydalıdır. Büyük veri kümeleri için en hızlı sıralama algoritması olmasa da, küçük dizilerde veya zaten neredeyse sıralı olan dizilerde iyi performans gösterir.

Giriş

Sıralama, bilgisayar bilimindeki en önemli işlemlerden biridir. Geliştiriciler, sayıları, adları, tarihleri, fiyatları, puanları, arama sonuçlarını, veritabanı kayıtlarını veya karşılaştırılabilir herhangi bir değer koleksiyonunu düzenlemeleri gerektiğinde sıralamayı kullanır.

Kabarcık Sıralama (Bubble Sort) ve Seçmeli Sıralama (Selection Sort) gibi temel sıralama algoritmalarını öğrendikten sonra, Ekleme Sıralama geliştiricilere başka önemli bir fikir sunar: komşu değerleri tekrar tekrar değiştirmek veya en küçük elemanı aramak yerine, algoritma her değeri doğru yerine ekler, tıpkı insanların ellerindeki iskambil kartlarını düzenlemesi gibi.

Bu, Ekleme Sıralama'yı çok sezgisel bir algoritma yapar. Yeni bir değer seçildiğinde, kendinden önceki değerlerle karşılaştırılır. Önceki değerler daha büyükse, doğru konum bulunana kadar sağa kaydırılırlar.

Ekleme Sıralama Nedir?

Ekleme Sıralama, diziyi iki parçaya ayıran bir sıralama algoritmasıdır: sıralı bir kısım ve sıralı olmayan bir kısım. Başlangıçta, ilk eleman sıralı kabul edilir. Ardından algoritma bir sonraki elemanı alır ve sıralı kısmın içine doğru konumuna ekler.

Her eleman doğru konumuna eklenene kadar bu süreç devam eder.

Ana fikir basittir:

  • İkinci elemandan başlayın.

  • Kendinden önceki elemanlarla karşılaştırın.

  • Daha büyük elemanları bir pozisyon sağa kaydırın.

  • Mevcut elemanı doğru konumuna ekleyin.

  • Dizi sıralanana kadar tekrarlayın.

Ekleme Sıralama'ya "ekleme" denmesinin nedeni, her elemanın dizinin sıralı kısmındaki doğru yerine eklenmesidir.

Ekleme Sıralama Nasıl Çalışır?

Ekleme Sıralama, dizinin sıralı kısmını kademeli olarak genişleterek çalışır. Algoritma, tek bir eleman her zaman kendi kendine sıralı olduğu için, ilk elemanın zaten sıralı olduğunu varsayar.

Ardından ikinci elemanla başlar ve onu mevcut değer olarak saklar. Algoritma bu mevcut değeri kendinden önceki elemanlarla karşılaştırır. Daha önceki bir eleman mevcut değerden büyükse, o önceki eleman sağa kaydırılır.

Doğru konum bulunduğunda, mevcut değer oraya yerleştirilir. Bu, tüm elemanlar işlenene kadar devam eder.

Basitçe söylemek gerekirse, Ekleme Sıralama tekrarlayan bir soru sorar:

Bu mevcut eleman, zaten sıralı olan kısma nereye eklenmelidir?

Manuel Çalışma Örneği

Aşağıdaki diziyi Ekleme Sıralama kullanarak manuel olarak sıralayalım:

[5, 3, 8, 4, 2]

Başlangıçta, ilk eleman sıralı kabul edilir:

Sorted part:   [5]
Unsorted part: [3, 8, 4, 2]

Adım 1

Mevcut eleman 3'tür. Bunu önceki eleman 5 ile karşılaştırırız.

5, 3'ten büyük olduğu için 5'i bir pozisyon sağa kaydırırız.

Before insertion:
[5, 3, 8, 4, 2]

Shift 5 to the right:
[5, 5, 8, 4, 2]

Insert 3:
[3, 5, 8, 4, 2]

Şimdi sıralı kısım:

[3, 5]

Adım 2

Mevcut eleman 8'dir. Bunu 5 ile karşılaştırırız.

5, 8'den büyük olmadığı için kaydırma gerekmez. 8 elemanı zaten doğru konumdadır.

Before insertion:
[3, 5, 8, 4, 2]

After insertion:
[3, 5, 8, 4, 2]

Şimdi sıralı kısım:

[3, 5, 8]

Adım 3

Mevcut eleman 4'tür. Bunu sıralı kısımdaki önceki elemanlarla karşılaştırırız.

Önce, 8, 4'ten büyük olduğu için 8 sağa kaydırılır. Ardından 5, 4'ten büyük olduğu için 5 sağa kaydırılır. 3 değeri 4'ten büyük olmadığı için 4'ü 3'ten sonra ekleriz.

Before insertion:
[3, 5, 8, 4, 2]

Shift 8:
[3, 5, 8, 8, 2]

Shift 5:
[3, 5, 5, 8, 2]

Insert 4:
[3, 4, 5, 8, 2]

Şimdi sıralı kısım:

[3, 4, 5, 8]

Adım 4

Mevcut eleman 2'dir. Bunu sıralı kısımdaki tüm önceki elemanlarla karşılaştırırız.

8, 5, 4 ve 3'ün hepsi 2'den büyük olduğu için her biri sağa kaydırılır. Ardından 2 en başa eklenir.

Before insertion:
[3, 4, 5, 8, 2]

Shift 8:
[3, 4, 5, 8, 8]

Shift 5:
[3, 4, 5, 5, 8]

Shift 4:
[3, 4, 4, 5, 8]

Shift 3:
[3, 3, 4, 5, 8]

Insert 2:
[2, 3, 4, 5, 8]

Dizi şimdi sıralanmıştır.

Son Sıralı Dizi

[2, 3, 4, 5, 8]

Bu manuel çalışma, Ekleme Sıralama'nın temel davranışını göstermektedir. Algoritma, Seçmeli Sıralama gibi en küçük elemanı aramaz. Bunun yerine, her seferinde bir eleman alır ve onu önceki elemanlar arasına doğru konumuna ekler.

Ekleme Sıralama Algoritması Adımları

Algoritma şu adımlar kullanılarak açıklanabilir:

  1. İlk elemanın zaten sıralı olduğunu varsayın.

  2. İkinci elemandan başlayın.

  3. Mevcut elemanı geçici bir değişkende saklayın.

  4. Mevcut elemanı kendinden önceki elemanlarla karşılaştırın.

  5. Daha büyük elemanları bir pozisyon sağa kaydırın.

  6. Mevcut elemanı doğru konumuna ekleyin.

  7. Dizinin sonuna kadar tekrarlayın.

Bu adım adım davranış, Ekleme Sıralama'yı basit ve tahmin edilebilir kılar.

Sözde Kod (Pseudocode)

for i from 1 to length(array) - 1:
    current = array[i]
    j = i - 1

    while j >= 0 and array[j] > current:
        array[j + 1] = array[j]
        j = j - 1

    array[j + 1] = current

Dış döngü, sıralanmamış kısımdan her elemanı seçer. İç döngü, doğru ekleme konumu bulunana kadar daha büyük elemanları sağa kaydırır.

PHP'de Ekleme Sıralama Örneği

İşte Ekleme Sıralama'nın temiz bir PHP uygulaması:

<?php

function insertionSort(array $numbers): array
{
    $length = count($numbers);

    for ($i = 1; $i < $length; $i++) {
        $current = $numbers[$i];
        $j = $i - 1;

        while ($j >= 0 && $numbers[$j] > $current) {
            $numbers[$j + 1] = $numbers[$j];
            $j--;
        }

        $numbers[$j + 1] = $current;
    }

    return $numbers;
}

$numbers = [5, 3, 8, 4, 2];

$sortedNumbers = insertionSort($numbers);

print_r($sortedNumbers);

Çıktı şöyle olacaktır:

Array
(
    [0] => 2
    [1] => 3
    [2] => 4
    [3] => 5
    [4] => 8
)

Bu uygulama, dizinin sıralı bir versiyonunu oluşturur ve onu döndürür. Kaydırma işlemi while döngüsü içinde gerçekleşirken, son ekleme döngü bittikten sonra olur.

JavaScript'te Ekleme Sıralama Örneği

İşte aynı algoritmanın JavaScript'te uygulanmış hali:

function insertionSort(numbers) {
    for (let i = 1; i < numbers.length; i++) {
        const current = numbers[i];
        let j = i - 1;

        while (j >= 0 && numbers[j] > current) {
            numbers[j + 1] = numbers[j];
            j--;
        }

        numbers[j + 1] = current;
    }

    return numbers;
}

const numbers = [5, 3, 8, 4, 2];

console.log(insertionSort(numbers));

Çıktı şöyle olacaktır:

[2, 3, 4, 5, 8]

JavaScript versiyonu, PHP versiyonu ile aynı mantığı takip eder. Sözdizimi değişse de, algoritmik fikir tamamen aynı kalır.

Ekleme Sıralama Neden Takas Etmek Yerine Kaydırır?

Ekleme Sıralama genellikle elemanları tekrar tekrar takas etmek yerine kaydırır. Bu, algoritmayı anlamayı kolaylaştırır ve genellikle birçok takas yapmaktan daha verimlidir.

Mevcut değer, önceki değerlerden daha küçük olduğunda, algoritma o önceki değerleri bir pozisyon sağa kaydırır. Doğru pozisyon açıldıktan sonra, mevcut değer oraya eklenir.

Örneğin, 4'ü bu sıralı kısma eklersek:

[3, 5, 8]

Algoritma 8 ve 5'i sağa kaydırır, ardından 4'ü 3 ile 5 arasına yerleştirir:

[3, 4, 5, 8]

Bu davranış, elinizdeki kartları düzenlemeye benzer. Yeni kart için yer açar, sonra onu doğru konuma yerleştirirsiniz.

Ekleme Sıralama'nın Zaman Karmaşıklığı

Zaman karmaşıklığı, bir algoritmanın çalışma süresinin giriş boyutu arttıkça nasıl büyüdüğünü açıklar. Ekleme Sıralama için performans, giriş dizisinin ne kadar sıralı olduğuna büyük ölçüde bağlıdır.

Ekleme Sıralama'nın üç önemli zaman karmaşıklığı durumu vardır:

  • En iyi durum: O(n)

  • Ortalama durum: O(n²)

  • En kötü durum: O(n²)

Bu durumlar, iç döngünün elemanların sırasına bağlı olarak çok az veya çok kez çalışabilmesi nedeniyle ortaya çıkar.

En İyi Durum Zaman Karmaşıklığı: O(n)

En iyi durum, dizi zaten sıralı olduğunda gerçekleşir.

[1, 2, 3, 4, 5]

Bu durumda, her mevcut eleman kendinden önceki elemandan zaten büyüktür. Algoritma her elemanı yine de bir kez kontrol eder, ancak hiçbir şeyi kaydırmasına gerek kalmaz.

Algoritma dizide sadece basit bir geçiş yaptığı için, en iyi durum zaman karmaşıklığı şöyledir:

O(n)

Bu, Ekleme Sıralama'nın avantajlarından biridir. Veri zaten sıralı veya neredeyse sıralı olduğunda çok verimli olabilir.

Ortalama Durum Zaman Karmaşıklığı: O(n²)

Ortalama durum, elemanlar rastgele sırada olduğunda gerçekleşir.

[5, 1, 4, 2, 8]

Bu durumda, bazı elemanlar küçük kaydırmalara ihtiyaç duyarken, diğerleri daha büyük kaydırmalara ihtiyaç duyabilir. Ortalama olarak, her eleman birkaç önceki elemanla karşılaştırılabilir.

Dizi büyüdükçe, karşılaştırma ve kaydırma sayısı kabaca karesel olarak artar. Bu nedenle, ortalama durum zaman karmaşıklığı şöyledir:

O(n²)

Bu, Ekleme Sıralama'nın rastgele sıradaki büyük diziler için yavaşladığı anlamına gelir.

En Kötü Durum Zaman Karmaşıklığı: O(n²)

En kötü durum, dizi ters sırada sıralandığında gerçekleşir.

[5, 4, 3, 2, 1]

Bu durumda, her yeni elemanın sıralı kısmın en başına kadar taşınması gerekir. Bu, maksimum sayıda karşılaştırma ve kaydırma oluşturur.

Örneğin, ikinci eleman bir kaydırma, üçüncü eleman iki kaydırma, dördüncü eleman üç kaydırma ve bu şekilde devam eden kaydırmalara ihtiyaç duyabilir.

Yapılan toplam iş yaklaşık olarak şöyle olur:

1 + 2 + 3 + ... + (n - 1)

Bu n² olarak büyür, bu yüzden en kötü durum zaman karmaşıklığı şöyledir:

O(n²)

Ekleme Sıralama'nın Alan Karmaşıklığı

Ekleme Sıralama, elemanları sıralamak için ek bir diziye ihtiyaç duymaz. Sadece mevcut değer ve indeks sayaçları gibi birkaç ek değişken kullanır.

Bu nedenle, alan karmaşıklığı şöyledir:

O(1)

Bu, Ekleme Sıralama'nın yerinde (in-place) bir sıralama algoritması olduğu anlamına gelir. Diziyi sabit ek bellek kullanarak sıralar.

Ekleme Sıralama Kararlı (Stable) mıdır?

Ekleme Sıralama, doğru uygulandığında kararlı bir sıralama algoritmasıdır.

Kararlı bir sıralama algoritması, eşit elemanların göreceli sırasını korur. Örneğin, iki öğrencinin aynı notu varsa, kararlı bir sıralama onları sıralamadan önceki aynı göreceli sırada tutar.

Ekleme Sıralama kararlıdır çünkü sadece mevcut elemandan büyük olan elemanları kaydırır. Karşılaştırma şunu kullandığında eşit elemanları birbirinin önüne geçirmez:

array[j] > current

Eğer karşılaştırma şuna değiştirilirse:

array[j] >= current

o zaman algoritma kararsız hale gelebilir çünkü eşit değerler gereksiz yere kaydırılabilir.

Ekleme Sıralama ve Kabarcık Sıralama Karşılaştırması

Ekleme Sıralama ve Kabarcık Sıralama (Bubble Sort) her ikisi de basit sıralama algoritmalarıdır ve her ikisinin de ortalama ve en kötü durum zaman karmaşıklığı O(n²)'dir. Ancak, Ekleme Sıralama, küçük veya neredeyse sıralı veri kümeleri için genellikle daha pratiktir.

Kabarcık Sıralama, komşu elemanları tekrar tekrar karşılaştırır ve yanlış sıradalarsa yerlerini değiştirir. Ekleme Sıralama ise sıralı bir kısım oluşturur ve her yeni elemanı doğru yerine ekler.

Uygulamada, Ekleme Sıralama genellikle Kabarcık Sıralama'dan daha az işlem yapar çünkü elemanları bitişik değerleri tekrar tekrar takas etmek yerine doğrudan konumlarına kaydırır.

Ekleme Sıralama ve Seçmeli Sıralama Karşılaştırması

Seçmeli Sıralama (Selection Sort), sıralı olmayan kısımdaki en küçük elemanı tekrar tekrar bulur ve onu başlangıca yerleştirir. Ekleme Sıralama ise her seferinde bir eleman alır ve onu sıralı kısma ekler.

Her iki algoritmanın da O(n²) ortalama ve en kötü durum zaman karmaşıklığı vardır, ancak farklı davranırlar.

  • Seçmeli Sıralama daha az takas yapar.

  • Ekleme Sıralama, neredeyse sıralı verilerde daha iyi performans gösterir.

  • Ekleme Sıralama, doğru uygulandığında kararlıdır.

  • Seçmeli Sıralama, değiştirilmediği sürece genellikle kararlı değildir.

  • Ekleme Sıralama, doğru konum bulunduğunda kaydırmayı erken durdurabilir.

Bu, Ekleme Sıralama'yı Seçmeli Sıralama'dan daha uyarlanabilir kılar.

Geliştiriciler Ekleme Sıralama'yı Ne Zaman Kullanmalı?

Geliştiriciler, veri kümesi küçük, neredeyse sıralı olduğunda veya yüksek performanstan çok basitlik önemli olduğunda Ekleme Sıralama'yı kullanmalıdır.

Ekleme Sıralama şu durumlarda faydalıdır:

  • Dizi boyutu küçüktür.

  • Veriler zaten neredeyse sıralıdır.

  • Algoritmanın basit ve anlaşılması kolay olması gerekir.

  • Ek bellek kullanımı minimum olmalıdır.

  • Kararlı bir sıralama algoritmasına ihtiyaç vardır.

  • Sıralama işlemi, eğitsel bir örneğin parçasıdır.

Büyük veri kümeleri için geliştiriciler genellikle Birleştirme Sıralama (Merge Sort), Hızlı Sıralama (Quick Sort), Yığın Sıralama (Heap Sort) gibi daha verimli algoritmaları veya programlama dillerinin sağladığı yerleşik sıralama fonksiyonlarını tercih ederler.

Ekleme Sıralama Ne Zaman Kullanılmamalı?

Ekleme Sıralama, performansın önemli olduğu büyük rastgele veri kümelerini sıralarken kullanılmamalıdır. Ortalama ve en kötü durum zaman karmaşıklığı O(n²) olduğu için, giriş boyutu büyüdükçe algoritma yavaşlayabilir.

Örneğin, 10 elemanı Ekleme Sıralama ile sıralamak basit ve hızlıdır. 1.000.000 rastgele elemanı Ekleme Sıralama ile sıralamak genellikle kötü bir fikirdir çünkü karşılaştırma ve kaydırma sayısı aşırı derecede artabilir.

Üretim sistemlerinde, geliştiriciler genellikle, bir sıralama algoritmasını manuel olarak uygulamak için belirli bir nedenleri olmadıkça, optimize edilmiş yerleşik sıralama fonksiyonlarını kullanmalıdır.

Ekleme Sıralama Uygulanırken Yapılan Yaygın Hatalar

Algoritma dikkatli indeks yönetimi gerektirdiğinden, yeni başlayanlar Ekleme Sıralama'yı uygularken sık sık hata yaparlar.

Yaygın hatalar şunlardır:

  • Dış döngüyü indeks 1 yerine indeks 0'dan başlatmak.

  • Elemanları kaydırmadan önce mevcut değeri saklamayı unutmak.

  • While döngüsü içinde yanlış karşılaştırma koşulu kullanmak.

  • Kaydırdıktan sonra mevcut değeri eklemeyi unutmak.

  • Döngü içinde yanlış indeksi azaltmak.

  • >= yerine > kullanmak ve kararlılığı kaybetmek.

En önemli detay, kaydırmadan önce mevcut değeri saklamaktır. Aksi takdirde, kaydırma işlemi sırasında değerin üzerine yazılabilir.

Pratik Örnek: Ürün Fiyatlarını Sıralama

Birkaç ürün fiyatının en düşüğünden en yükseğine doğru sıralanması gereken küçük bir e-ticaret özelliğini düşünün. Ürün sayısı azsa, Ekleme Sıralama sorunu basit bir şekilde çözebilir.

<?php

$prices = [49.99, 19.99, 99.99, 29.99];

function sortPrices(array $prices): array
{
    for ($i = 1; $i < count($prices); $i++) {
        $currentPrice = $prices[$i];
        $j = $i - 1;

        while ($j >= 0 && $prices[$j] > $currentPrice) {
            $prices[$j + 1] = $prices[$j];
            $j--;
        }

        $prices[$j + 1] = $currentPrice;
    }

    return $prices;
}

print_r(sortPrices($prices));

Sıralanmış sonuç şöyle olacaktır:

[19.99, 29.99, 49.99, 99.99]

Bu örnek basit olsa da, Ekleme Sıralama'nın gerçek uygulama verilerine nasıl bağlanabileceğini gösterir.

Ekleme Sıralama'yı Anlamak İçin Pratik Kontrol Listesi

Daha gelişmiş sıralama algoritmalarına geçmeden önce, geliştiriciler şu soruları yanıtlayabilmelidir:

  • Ekleme Sıralama neden ikinci elemandan başlar?

  • Sıralı kısım ile sıralı olmayan kısım arasındaki fark nedir?

  • Kaydırmadan önce mevcut değeri neden saklarız?

  • İç while döngüsü ne zaman durur?

  • En iyi durum neden O(n)'dir?

  • En kötü durum neden O(n²)'dir?

  • Alan karmaşıklığı neden O(1)'dir?

  • Ekleme Sıralama neden kararlıdır?

Bu noktalar netse, geliştirici Ekleme Sıralama'nın arkasındaki gerçek mantığı anlamış demektir, sadece kodu ezberlememiş demektir.

Ekleme Sıralama'nın Avantajları

Ekleme Sıralama'nın belirli durumlarda onu faydalı kılan çeşitli avantajları vardır.

  • Anlaşılması ve uygulanması basittir.

  • Küçük veri kümelerinde iyi performans gösterir.

  • Neredeyse sıralı diziler için verimlidir.

  • Yerinde (in-place) bir sıralama algoritmasıdır.

  • Doğru uygulandığında kararlıdır.

  • En iyi durum zaman karmaşıklığı O(n)'dir.

Bu avantajlar, onu eğitim ve küçük pratik durumlar için iyi bir algoritma yapar.

Ekleme Sıralama'nın Dezavantajları

Ekleme Sıralama'nın önemli sınırlamaları da vardır.

  • Büyük rastgele veri kümeleri için verimsizdir.

  • Ortalama durum zaman karmaşıklığı O(n²)'dir.

  • En kötü durum zaman karmaşıklığı O(n²)'dir.

  • Dizi tersine çevrildiğinde birçok kaydırma gerektirebilir.

  • Büyük girdiler için gelişmiş sıralama algoritmalarından genellikle daha yavaştır.

Bu sınırlamalar nedeniyle, Ekleme Sıralama genellikle büyük ölçekli üretim sıralaması için en iyi seçenek değildir.

Sonuç

Ekleme Sıralama, sıralı diziyi her seferinde bir eleman ekleyerek oluşturan basit ve pratik bir sıralama algoritmasıdır. Sıralı olmayan kısımdaki her elemanı alıp, sıralı kısmın içine doğru konumuna yerleştirerek çalışır.

Algoritma, kartları sıraya koyma gibi davrandığı için anlaşılması kolaydır. Daha büyük elemanları sağa kaydırır ve mevcut elemanı ait olduğu yere yerleştirir.

Ekleme Sıralama'nın dizi zaten sıralı olduğunda en iyi durum zaman karmaşıklığı O(n), ortalama ve en kötü durum zaman karmaşıklığı ise O(n²)'dir. Alan karmaşıklığı O(1)'dir, bu da ek bellek gerektirmeden yerinde sıralama yaptığı anlamına gelir.

Ekleme Sıralama, büyük rastgele veri kümeleri için ideal olmasa da, algoritmik düşünmeyi öğrenmek, karşılaştırmaları ve kaydırmaları anlamak ve küçük veya neredeyse sıralı dizileri işlemek için mükemmeldir. Veri yapıları ve algoritmaları inceleyen geliştiriciler için Ekleme Sıralama, daha gelişmiş sıralama tekniklerini anlamaya yönelik önemli bir adımdır.