Özellikler:

  • Uygulaması kolaydır.
  • Küçük Veri kümeleri üzerinde kullanıldığında verimlidir.
  • Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir.
  • Karmaşıklığı 010a4978e9a370acc652fba403070892[1] seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir.
  • Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez)
  • Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez. Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur.
  • Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir.

 

Çalışma mantığı çok basittir:

Sıralanmak istenen dizinin en başındaki elemandan en sonundakine kadar tüm verileri tek tek kontrol eder ve gerekli yerlere yerleştirir.

Kontrol edeceğimiz değerimizi geçici olarak kaydederiz. Daha sonra kontrol ettiğimiz eleman indisinden itibaren geriye doğru gideriz.

Eğer, geçici olarak tuttuğumuz değer, o anda üzerinde bulunduğumuz değerden küçükse, bir basamak önce üzerinde olduğumuz yere yazarız. Bu sayede sayıyı bir sağa kaydırmış oluruz. Fakat daha sonrasında geçici olarak tuttuğumuz (kontrol edilen) değeri şu anda üzerinde bulunduğumuz yere yazmamız gerekmektedir.

Kısaca dizinin başından sonuna doğru giderken

Bir şekilde anlatmak gerekirse:

 fig4[1]

Pseudocode:

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j - 1;
            if j < 0 then exit while;
        end;
        A[j + 1] := value;
    end;
end;

 

Örnek C++ Kodu:

void insertionsort(int *a, int n)
{
      int i, j, t;
      for (i=1; i<n; i++)
      {
          j=i;
          t=*(a+j);
          while (j>0 && *(a+j-1)>t)
          {
              *(a+j)=*(a+j-1);
              j--;
          }
          *(a+j)=t;
      }
} 

 

Kaynaklar:
www.wikipedia.org
www.javacoffeebreak.com

Tags: , | Categories: Algoritma | C++