Home / Algoritmalar / Insertion Sort Algoritması (Sokma Sıralama) – Örnek – C Kodu

Insertion Sort Algoritması (Sokma Sıralama) – Örnek – C Kodu

Insertion Sort Türkçeye Sokma Sıralama ya da Araya Sokma sıralaması şeklinde çevrilmiştir. Temel mantığı işlenen sayının doğru pozisyona yerleştirilmesi üzerinedir. Bu işlem yapılırken dizi üzerinde sık sık kaydırma yapılır ve doğru pozisyona ilgili sayı yerleştirilir.

Bubble Sort ve Selection Sort’a nazaran biraz karışık görülebilir, ancak göreceksiniz ki oldukça basit bir sıralama mantığı bulunmaktadır. Örnek üzerinde anlatacağımız gibi, C Kodu üzerinde de anlatımı yapılacaktır.

Insertion Sort Pseudo (sözde Kod) Kod

1- bir sayıyı eline al solundaki sayılara bak

2- Soldaki sayı elindeki sayıdan büyükse bir sağa kaydır.

3- Kendisinden küçük sayı bulunca boş bulunan indise yerleştir.

4- Diğer sayıya geç.

Burada dikkat etmeniz gereken 1. adım, 1. indisten başlar (0. indis değil)

Insertion Sort Algoritması Örnek

Not: Yukarıdaki örnek wikipedia’dan alınmıştır.

Yukarıda verdiğimiz örnek üzerinden gidelim. Dikkat ettiyseniz 1. indisten başlıyor ve solundaki sayıları işlemeye başlıyor. Temel şart solundaki sayı eğer kendisinden büyükse bu sayıyı sağa kaydırıyor. Dizilerde sağa kaydırmak demek dizi[i+1] = dizi[i] demektir. Tabii elimizde tuttuğumuz sayıyı ayrı bir değişkene atamayı unutmayacağız. Peki ne oluyor örnekte?

Sayılarımız “6 5 3 1 8 7 2 4

Alttaki örneğimizdeki yeşil sayılar yerleştirilmiş olan sayılar, kırmızı sayılar ise kayan (sağa) sayılardır. Koyu sayılar ise sabittir.

  1. Adım: 1. indisten başla solundaki sayılara bak, eğer soldaki sayı sağdaki sayıdan büyükse bu sayıyı bir kaydır. eldeki sayıyı (5) uygun pozisyona yerleştir. Yani 6 sağa kayarken 5 soluna yerleştirilir. 5 6 3 1 8 7 2 4
  2. Adım: 2. İndise geçelim. (3) solundaki ilk sayı 6, sağa bir adım kayar. solundaki diğer sayı 5 o da sağa bir kayar. Başka sayı olmadığına göre 3 sayısı dizinin sıfırıncı indisine yerleştirilir. 3 5 6 1 8 7 2 4
  3. Adım: 3. indise geçecelim (1). solundaki sayılardan 6, 5 ve 3 sayıları 1’den büyük olduğu için hepsi sağa kayar. 1 ise en başa yerleşir.  1 3 5 6 8 7 2 4
  4. Adım: 4. indise geçiyoruz. (8). solundakisayılardan hiçbirisi kendisinden büyük olmadığı için aynı yerinde kalır. 1 3 5 6 8 7 2 4
  5. Adım: 5. indiste 7 sayısı var. solundaki sayılardan bir tek 8 sayısı kendisinden büyük. Bu yüzden 8 sayısı bir sağa kayar, 7 sayısı bu pozisyona yerleşir. 1 3 5 6 7 8 2 4
  6. Adım: 6. indiste 8 sayısı var. O yine aynen kalır. Çünkü solundaki hiçbir sayı kendisinden büyük değil. (hepsini karşılaştırmaya gerek yok, solundaki sayı kendisinden küçükse diğer sayılara bakmayız) 1 3 5 6 7 8 2 4
  7. Adım: 7. indiste 2 sayısı var. 2 sayısı tek tek solundaki sayılarla karşılaştırılır ve 2 sayısından büyük olan tüm sayılar sağa kayar. 2 sayısı kendisinden küçük bir sayı ile karşılaşıncaya kadar karşılaştırılmaya devam eder. 1 2 3 5 6 7 8 4 1 sayısı görülünce karşılaştırma durur ve 2 sayısı bu pozisyona yerleştirilir.
  8. Adım: 8. indiste 4 sayısı var. Solundaki sayılarla karşılaştırma yapılır. 5, 6, 7, 8 sayıları dörtten büyük olduğu için birer indis sağa kayar ve 4 sayısı üçün önüne yerleşir. 1 2 3 4 5 6 7 8

Hop sayılar sıralanmış oldu. Şimdi bunun bir de C kodu neymiş onu inceleyelim.

Insertion Sort Algoritması C Kodu


#include <stdio.h>
#define SIZE 10000

int myArray[SIZE - 1];

//Esas fonksiyonumuz burası parametre olarak dizi alıyor.
void insertionSort(int x[])
{
    //dış döngümüz ve içteki while döngümüz için değişkenler
    int i, j;
    //Anahtar indisimiz için değişken
    int key;

    //Sitemizdeki örnekte anlattığımız gibi 1. indisten başlıyor döngümüz
    for(i = 1; i < SIZE; i++) { //indisteki sayımız anahtar değerimiz oluyor. key = myArray[i]; //Anahtar değerimizin bir solundaki sayıyının indisine j dedik j = i - 1; //Eğer j büyük eşittir sıfır ve dizi[j] sayımız anahtar değerden büyükse bu sayıların hepsini sağa kaydıracağız. while(j >= 0 && myArray[j] > key)
        {
            //Kaydırma işini burada yapıyoruz.
            myArray[j+1] = myArray[j];

            //J'nin eksilmesi soldaki sayıları taramak için
            j--;
        }

        //Bu satır doğru pozisyona eleman ekleme işlemini gerçekleştiriyor.
        myArray[j+1] = key;
    }
}

void printSorted()
{
    int i;
    for( i = 0; i < SIZE - 1; i++)
    {
        printf("%d\n", myArray[i]);
    }
}

void swapf(int x, int y)
{
    int temp;
    temp = myArray[x];
    myArray[x] = myArray[y];
    myArray[y] = temp;

}

void init()
{
    int i;
    for( i = 0; i < SIZE - 1; i++)
    {
        myArray[i] = rand()%10000;
    }
}

int main()
{
    init();
    insertionSort(myArray);
    printSorted();
    return 0;
}

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir