Bu yazımızda insertion sort (ekleme sıralaması) algoritması hakkında bilgiler vereceğiz.

Insertion Sort (Ekleme Sıralaması) Algoritması Nedir ?

Insertion sort, bir dizi içindeki nesneleri sıralamak için kullanılan basit bir sıralama algoritmasıdır. Algoritma, dizinin her bir elemanını sıralanmış bir kısmına eklemek için kullanır. Bu kısım, ilk elemandan başlayarak, her seferinde bir eleman daha büyük hale gelir.

Insertion Sort (Ekleme Sıralaması) Nasıl Çalışır ?

Insertion sort algoritması, diziyi sıralamak için iki farklı döngü kullanır. İlki, dizinin her bir elemanını işlemek için kullanılır ve ikincisi, sıralanmış kısımdaki elemanlar arasında arama yapmak için kullanılır.

  1. Adım: Dizinin ilk elemanını sıralanmış kısım olarak kabul ederiz.
  2. Adım: Dizinin ikinci elemanı alınır ve sıralanmış kısımdaki elemanlar arasında arama yapılır. Eğer ikinci eleman, sıralanmış kısımdaki elemanlardan daha küçükse, doğru yere yerleştirilir.
  3. Adım: Dizinin üçüncü elemanı alınır ve sıralanmış kısımdaki elemanlar arasında arama yapılır. Eğer üçüncü eleman, sıralanmış kısımdaki elemanlardan daha küçükse, doğru yere yerleştirilir.
  4. Adım: Dizinin dördüncü elemanı alınır ve sıralanmış kısımdaki elemanlar arasında arama yapılır. Eğer dördüncü eleman, sıralanmış kısımdaki elemanlardan daha küçükse, doğru yere yerleştirilir.
  5. Adım: Bu işlem, dizinin son elemanına kadar devam eder.

Sonuç olarak, insertion sort algoritması, dizinin her bir elemanını tek tek dolaşır ve her elemanı doğru yere yerleştirir. Bu yerleştirme işlemi, sıralanmış kısımdaki elemanlar arasında arama yaparak gerçekleştirilir. Eleman, sıralanmış kısımdaki doğru yerine yerleştirildiğinde, sıralanmış kısım bir eleman daha büyük hale gelir.

Insertion Sort (Ekleme Sıralaması) Zaman Karmaşıklığı Nedir ?

Insertion Sort Algoritması genellikle O(n^2) zaman karışıklığına sahiptir. Bu, dizinin boyutu n olduğunda, algoritmanın n^2 adımda tamamlanabileceği anlamına gelir. Örneğin, dizinin boyutu 10 olduğunda, algoritma en fazla 100 adımda tamamlanabilir.

Bu yazı dikkatini çekebilir.   Sıralama Algoritmaları – Merge Sort (Birleştirme Sıralaması) Algoritması

Bu zaman karışıklığı, algoritmanın her bir elemanı sıralanmış kısımdaki yerine yerleştirmek için arama yapmasından kaynaklanır. Her eleman için arama, en fazla dizinin boyutu kadar adım gerektirebilir. Böylece, algoritma tüm elemanlar için arama yaptığında, en fazla n*n adım gerekir.

Ancak, eğer dizi önceden sıralanmışsa, her elemanı yerleştirmek için arama yapmak gerekmez ve bu nedenle algoritma O(n) zaman karışıklığına sahip olur. Bu nedenle Insertion sort daha çok presorted verilerde kullanılır.

Insertion Sort (Ekleme Sıralaması) Örnek Kullanımı

Şimdide c programlama dili ile yazılımış örnek bir insertion sort kodunu görelim.

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printf("Sıralanmış dizi: \n");
    printArray(arr, n);

    return 0;
}

Bu kod, bir dizi oluşturur ve insertionSort() fonksiyonunu kullanarak diziyi sıralar. insertionSort() fonksiyonu, dizinin her elemanını sıralanmış kısımdaki yerine yerleştirmek için arama yapar. printArray() fonksiyonu, sıralanmış diziyi ekrana yazdırır.

Çıktısı : 

Sıralanmış dizi: 
5 6 11 12 13

Bu yazımızda insertion sort (ekleme sıralaması) algoritması hakkında bilgiler verdik. Diğer veri yapıları konulu yazılarımızı okumak için buraya tıklayabilirsiniz.