Sıralama Algoritmaları

Sıralama algoritması nedir?

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, herhangi bir sayıdaki tip verilerin sınırlı bellek ve işlem gücü ile belirli bir sıraya göre dizilmesinin sağlanmasıdır. Önemli olan en optimum bellek ve performans ikilisini verecek bir algoritmanın elde edilmesidir.

Sıralama algoritmaları nelerdir?

Seçme Sıralama (Selection Sort)

Seçmeli sıralama algoritması O(n²) grubuna giren bir sıralama yöntemidir. Dolayısıyla büyük sayıda verileri sıralamak için kullanışlı değildir.

Bu algoritmanın işleyişi şu şekildedir; Rastgele (random) olarak sıralanmış bir diziyi küçükten büyüğe doğru sıralamak istediğimizde, dizinin her döndürülmesinde en küçük elemanını seçerek en başa yazdırmaktadır. Yani birinci taramada bulunan en küçük eleman birinci sıraya; ikinci elemandan başlayarak yapılan ikinci taramada bulunan en küçük ikinci elaman ikinci sıraya vb. yerleştirirlerek sıralama işlemi tamamlanmaktadı.

for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

Kabarcık Sıralama (Bubble Sort)

Kabarcık sıralama, sıralama algoritmaları arasında yazılması en kolay olan, ama büyük dizilerde çok yavaş kalan ve O(n²) grubuna giren bir sıralama yöntemidir. 

Bu algoritmanın işleyişi şu şekildedir; Baştan sona veya sondan başa doğru komşu elemanlar karşılaştırılarak büyüklük küçüklük durumlarına göre yerleri değiştirilir. Komşu elemanların bu karşılaştırmalı taraması, dizinin eleman sayısı kadar tekrarlanır.

procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped
end procedure </gösterilebilir:

Kokteyl Sıralama (Cocktail Sort)

Çift yönlü kabarcık sıralama algoritması olan kokteyl sıralamada hem baştan sona doğru hem de sondan başa doğru taramalarla komşu elemanlar karşılaştırılarak sıralanır. O(n²) grubundadır. Bu sıralama algoritmasını uygulamak kabarcık sıralama algoritmasını uygulamaya göre daha zordur.

Bu algoritmanın işleyişi şu şekildedir; Baştan sona doğru taramada en büyük eleman sona gider ve sondan başa doğru olan taramada ise en küçük eleman başa gelmektedir.

procedure cocktailSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // ardışık iki öğenin doğru sırada olup olmadığına bak order
        swap( A[ i ], A[ i + 1 ] ) // iki öğenin yerlerini değiştir
        swapped := true
      end if
    end for
    if swapped = false then
      // eğer değişiklik yapılmadıysa dıştaki döngüden çıkabiliriz.
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // hiçbir öğe yer değiştirmediyse liste sıralanmıştır
end procedure

Tarak Sıralama (Comb Sort)

Kabarcık sıralama algoritmasından başarılıdır ve O(n log(n)) grubundadır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır. Bir nevi kabarcık ve hızlı sıralama algoritmalarının karışımı olarak da adlandırılır. Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır. Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir.

Bu algoritmanın işleyişi şu şekildedir; Kabarcık sıralama algoritmasında komşu elemanlar arasında karşılaştırmalara yapılmakta ve duruma göre yer değişikliği gerçekleştirilmekteydi. Ancak tarak sıralama algoritmasında ise komşu elemanlar arasında değil belirlenen mesafedeki daha uzak elemanlar arasında bu karşılaştırmalar ve yer değişiklikleri yapılmaktadır. Dolayısıyla kabarcık sıralama algoritması, mesafenin bir(1) olduğu tarak sıralama algoritması olarak değerlendirilebilir.

function combsort11(array input)
    gap := input.size //öğeler arasındaki aralığın başlangıç boyutunu belirle
    
    loop until gap <= 1 or swaps = 0
        //yeni bir tarama için aralığın boyutunu güncelle
        if gap > 1
            gap := gap / 1.3
            if gap = 10 or gap = 9
                gap := 11
            end if
        end if
        

        i := 0
        swaps := 0 // Açıklama için kabarcık sıralamasına bakınız
        

        // giriş listesinin üzerinden tek bir "tarama"
        loop until i + gap >= array.size //Benzer yaklaşım için kabuk sıralamasına bakınız
            if array[i] > array[i+gap]
                swap(array[i], array[i+gap])
                swaps := 1 // Aritmetik taşma düzeltmesi için
            end if
            i := i + 1
        end loop
       

    end loop
end function

Araya Eklemeli Sıralama (Insertion Sort)

Sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır. Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır. Uygulaması kolaydır. Küçük Veri kümeleri üzerinde kullanıldığında ve çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir. Karmaşıklığı O(n²) olan seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından da daha verimlidir. 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.

Bu algoritmanın işleyişi şu şekildedir; Her eleman, kendinden önceki alt dizideki elemanlarla karşılaştırılmakta ve daha küçükse ilgili yerdeki araya yerleştirilmektedir. Yani rastlanan her küçük eleman dizideki araya girerek, diğer dizi elemanlarını sona doğru ittirmektedir.

insertionSort(array A)
    for i = 1 to length[A-1] do
        value = A[i]
        j = i-1
        while j >= 0 and A[j] > value
            A[j + 1] = A[j]
            j = j-1
        A[j+1] = value

Kabuk Sıralama (Shell Sort)

Donald Shell adında bir bilim insanı tarafından bulunan ve soyadıyla anılan bu algoritma, atlama payı 1 olan eklemeli sıralama algoritmasının geliştirilmiş halidir. Eklemeli sıralama algoritmasının aşağıdaki iki gözlem kullanılarak genelleştirilmiş biçimidir:

• Eklemeli sıralama, sıralanacak dizi zaten büyük oranda sıralıysa daha verimli çalışır.
• Eklemeli sıralama, dizideki öğeleri her adımda yalnızca bir sonraki konuma aktardığından verimsizdir.

Algoritma performansı O(n log²(n))’ dir.

Bu algoritmanın işleyişi şu şekildedir; Atlama payı birden küçük kalana kadar, dizi elemanlarını atlama payına göre karşılaştırarak sıralar.

# Bir diziyi a[0…n-1]sıralayın.
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# En büyük boşlukla başlayın ve 1’lik boşluğa kadar gidin.
foreach (gap in gaps)
{
    # Bu boşluk boyutu için boşluklu ekleme sıralaması yapın.
    # ilk boşluk ögeleri a[0..boşluk-1]zaten boşluklu sırada.
    # Tüm dizi boşluk sıralanana kadar bir öğe daha eklemeye devam edin 
    for (i = gap; i < n; i += 1)
    {
        # Aralıklı sıralanmış elemanlara bir [i] ekleyin.
        # a[i]’yi geçici olarak kaydedin ve i konumunda bir boşluk açın.
        temp = a[i]
        # Bir [i] için doğru konum bulunana kadar daha önce -boşluk sıralı öğeleri kaydırın.
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # geçici( orijinal a[i]) doğru yerine koyun.
        a[j] = temp
    }
}

Cüce Sıralama (Gnome Sort)

Eklemeli sıralamaya benzer bir sıralama algoritmasıdır. Eklemeli sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir. Cüce Sıralaması adı algoritmanın yönteminin mitolojideki Hollanda cücelerinin (gnome) bir dizi çiçek saksısını sıraya diziş biçimine benzemesinden kaynaklanmaktadır. O(n²) algoritma performansına sahiptir.

Bu algoritmanın işleyişi şu şekildedir; Yer değiştirme olmadığı (elemanların sıralı olduğu) sürece işlem ileriye doğru giderken, yer değiştirme oluştuğunda geriye doğru gitmektedir.

function gnomeSort(a[0..size-1]) {
i := 1
j := 2
while i < size - 1
  if a[i-1] >= a[i]
      i := j
      j := j + 1 
  else
      swap a[i-1] and a[i]
      i := i - 1
      if i = 0
         i := 1
}

Pankek Sıralama (Pancake Sort)

Bu algoritmanın işleyişi şu şekildedir: Pankek sıralama algoritmasında -seçme sıralama algoritmasına benzer şekilde dizi içindeki en büyük elemanı döndürme/çevirme işlemiyle en sona en sona yerleştirme esasına dayanmaktadır. Aynı şekilde en büyük ikinci eleman sondan ikinci; en büyük üçüncü eleman sondan üçüncü sıraya vb. döndürme işlemleriyle yerleştirilmektedir.

Öncelikle döndürme işlemini açıklayalaım.  A=[5,2,4,1,3] dizisi üzerinde “döndür (A,3)” komutu

şeklinde etki oluşturacaktır. Yani baştan belirtilen indise kadar olan kısmı döndürecektir.

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Rastgele Sıralama (Random Sort)

Yalnızca eğitim amaçlı olarak kullanılan verimsiz bir sıralama algoritmasıdır.

Bu algoritmanın işleyişi şu şekildedir; Sıralanacak veri dizisi rastgele dizilir ve sıralı olup olmadığı kontrol edilir. Bu rastgele dizilim ve kontrol, dizi sıralı hale gelinceye kadar devam eder.

while not InOrder(deck) do Shuffle(deck);

Birleştirmeli Sırlama (Merge Sort)

O (n log(n)) derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır.

Bu algoritmanın işleyişi şu şekildedir: Dizimiz, alt dizilere ayrıştırılarak her biri ayrı ayrı sıralanıp birleştirilmektedir. Yinelemeli olan bu algoritmanın çalışması aşağıdaki gibi özetlenebilir:

I. Diziyi eşit iki alt diziye ayır.

II. Bu ayırma işlemini, alt dizilerde en fazla 2 eleman kalıncaya kadar sürdür.

III. Alt dizileri kendi içinde büyükten küçüğe doğru sırala.

IV. Sıralı alt dizileri birleştir.

Sıralı iki alt dizi elemanları bitinceye kadar, sırada ki elemanları alınarak karşılaştırılır.

1. Her iki alt dizi elemanları bitinceye kadar, sıradaki elemanları alınarak karşılaştırılır.

1.1. Eğer birinci alt dizinin sırada ki elemanı, 2. alt dizinin sıradaki elemanından küçükse, oluşan birleştirilmiş dizinin sırada ki elemanı olarak atanır. 1. dizi için sıradaki elemanı gösteren indis ve oluşan birleştirilmiş dizinin indisi bir arttırılır.

1.2. Eğer 1. alt dizinin sıradaki elemanı, 2. dizinin sıradaki elemanından büyükse, 2. Alt dizinin sıradaki elemanı; oluşan birleştirilmiş dizinin sıradaki elemanı olarak atanır. 2. dizi için sıradaki elemanı gösteren indis ve oluşan birleştirilmiş dizinin indisi bir arttırılır.

2. Eğer herhangi  bir alt dizide sona ulaşılmamışsa; bu dizinin elemanları, oluşan birleştirilmiş diziye eklenir.

function mergesort(m)
   var list left, right
   if length(m) ≤ 1
       return m
   else
       middle = length(m) / 2
       for each x in m up to middle
           add x to left
       for each x in m after middle
           add x to right
       left = mergesort(left)
       right = mergesort(right)
       result = merge(left, right)
       return result

Hızlı Sıralama (Quick Sort)

n adet sayıyı, ortalama bir durumda, O(n log(n)) karmaşıklığıyla, en kötü durumda ise O (n²) karmaşıklığıyla sıralar. Yinelemeli olup sık kullanılır. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.

Bu algoritmanın işleyişi şu şekildedir; Belirli kriterlere göre pivot eleman seçilir. Diziyi 3 alt diziye ayrıştırır bunlar pivot elemandan küçük olan elemanları birinci (soldaki) diziye, pivot elemanı ikinci (ortadaki) diziye, pivot elemandan büyük olanları da üçüncü (sağdaki) diziye. Aynı işlemi birinci (soldaki) ve üçüncü (sağdaki) alt dizilere, tek elemanlı kalıncaya kadar uygulanır. Ve en son olarak sıralı alt dizileri birleştirir.

function quicksort(array)
     var list less, equal, greate
     if length(array) ≤ 1  
         return array  
     select a pivot value pivot from array
     for each x in array
         if x < pivot then append x to less
         if x = pivot then append x to equal
         if x > pivot then append x to greater
     return concatenate(quicksort(less), equal, quicksort(greater))

Kova Sıralama (Bucket Sort)

Kova Sıralaması (ya da sepet sıralaması), sıralanacak bir diziyi parçalara ayırarak sınırlı sayıdaki kovalara (ya da sepetlere) atan bir sıralama algoritmasıdır. Ayrışma işleminin ardından her kova kendi içinde ya farklı bir algoritma kullanılarak ya da kova sıralamasını özyinelemeli olarak çağırarak sıralanır.

Bu algoritmanın işleyişi şu şekildedir; Başlangıçta boş olan bir “kovalar” dizisi oluşturur. Asıl dizinin üzerinden geçerek her öğeyi ilgili aralığa denk gelen kovaya atar. Boş olmayan bütün kovaları sıralar. Ve boş olmayan kovalardaki bütün öğeleri yeniden diziye alır.

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

Yığın Sıralama (Heap Sort)

karşılaştırmaya dayalı bir sıralama algoritmasıdır. Uygulamada pek çok bilgisayarda hızlı sıralama algoritmasından daha yavaş çalışsa da en kötü durumda O(n log(n)) çalışma süresi vardır. Yığın sıralaması diziyi yerinde sıralar ancak kararlı bir sıralama algoritması değildir.

Bu algoritmanın işleyişi şu şekildedir; Karşılaştırma tabanlı olup, iki aşamalı yinelemeli bir algoritmadır. Birinci aşamada sıralı olmayan dizi, yığın düzeni haline getirilir. Yığın düzeni iki şekilde yapılabilir: maksimum ve minimum. Maksimum tabanlı yığın düzeninde; hiçbir düğüm, ata düğümünden büyük değer taşıyamaz. Yani ata düğümün değeri, çocuk düğümlerinden büyük olmak zorundadır.  Aynı şekilde minimum tabanlı yığın düzeninde de; hiçbir düğüm, ata değerinden küçük değer taşıyamamaktadır. (Ata düğümün değeri çocuk düğümlerden  küçük olmalıdır). İkinci aşamada ise, yığın düzeni haline getirilmiş dizinin kök/ilk elemanı, son elemanla yer değiştirir ve sonuncu elemanı içermeyen yeni dizi, yinelemeli olarak aynı işlemlere -dizi tamamlanıncaya kadar- devam edilir.

function heapSort(a, count) is
     input:  an unordered array a of length count
 
     (first place a in max-heap order)
     heapify(a, count)
 
     end := count - 1
     while end > 0 do
         (swap the root(maximum value) of the heap with the last element of the heap)
         swap(a[end], a[0])
         (decrease the size of the heap by one so that the previous max value will
         stay in its proper placement)
         end := end - 1
         (put the heap back in max-heap order)
         siftDown(a, 0, end)
 
 function heapify(a,count) is
     (start is assigned the index in a of the last parent node)
     start := (count - 1) / 2
     
     while start ≥ 0 do
         (sift down the node at index start to the proper place such that all nodes below
          the start index are in heap order)
         siftDown(a, start, count-1)
         start := start - 1
     (after sifting down the root all nodes/elements are in heap order)
 
 function siftDown(a, start, end) is
     input:  end represents the limit of how far down the heap
                   to sift.
     root := start

     while root * 2 + 1 ≤ end do          (While the root has at least one child)
         child := root * 2 + 1            (root*2+1 points to the left child)
         (If the child has a sibling and the child's value is less than its sibling's...)
         if child < end and a[child] < a[child + 1] then
             child := child + 1           (... then point to the right child instead)
         if a[root] < a[child] then       (out of max-heap order)
             swap(a[root], a[child])
             root := child                (repeat to continue sifting down the child now)
         else
             return

İplik Sıralama (Strand Sort)

Algoritmanın adı, sıralanacak dizinin içinden çıkan kendi içinde sıralanmış alt dizilerin ipliklere benzetilmesinden gelmektedir. İplik sıralaması algoritması, ana diziden ipleri çıkarırken ve oluşan sıralı ipleri birleştirirken karşılaştırma kullandığı için bir karşılaştırma sıralamasıdır. İplik sıralaması algoritmasının karmaşıklığı ortalamada O(n log(n))’dir. Sıralanacak dizinin zaten sıralı olduğu en iyi durumda algoritmanın karmaşıklığı O(n), sıralanacak dizinin tersten sıralı olduğu en kötü durumda ise algoritmanın karmaşıklığı O(n²)’dir

Bu algoritmanın işleyişi şu şekildedir; 1. adım sıralanacak dizinin üzerinden bir kere geçilir ve yükselen (sıralı) sayılar alınır. 2. adım sıralı olan alt dizi ilk yinelemenin ardından boş olan sıralanmış dizinin üstüne konur. 3. adım ana dizinin üzerinden yeniden geçilir ve kendi içinde sıralı yeni bir alt dizi çıkarılır. 4. adım artık sıralanmış dizi boş olmadığından yeni çıkarılan alt dizi sıralanmış diziyle birleştirilir. 5. adım alt dizi ve ana dizi boşalana kadar 3 ve 4. adımlar yinelenir.

procedure strandSort( A : list of sortable items ) defined as:
  while length( A ) > 0
    clear sublist
    sublist[ 0 ] := A[ 0 ]
    remove A[ 0 ]
    for each i in 0 to length( A ) do:
      if A[ i ] > sublist[ last ] then
        append A[ i ] to sublist
        remove A[ i ]
      end if
    end for
    merge sublist into results
  end while
  return results
end procedure

Kütüphane Sıralama (Library Sort)

Algoritma Michael A. Bender, Martín Farach-Colton, ve Miguel Mosteiro tarafından 2004’te geliştirilmiştir. Kütüphane sıralaması, aynı kendisinden türetildiği eklemeli sıralama gibi, kararlı bir karşılaştırma sıralamasıdır ve sıralamayı yaptığı sırada sıraladığı diziye yeni elemanlar eklenmesine izin verir. Ayrıca kütüphane sıralaması çoğu durumda eklemeli sıralama algoritmasının O(n²) karmaşıklığı yerine hızlı sıralama algoritmasının O(n log(n)) karmaşıklığına yaklaşmaktadır. Tek sorunu ise algoritmanın kullanıldığı aralıklar nedeniyle fazladan yere gereksinim duymasıdır.

Bu algoritmanın işleyişi şu şekildedir; Eklemeli sıralama algoritmasını art arda yapılan eklemeleri dizideki boşlukları kullanıp hızlandırarak kullanır.

 procedure rebalance(A, begin, end) is
    r ← end
    w ← end ÷ 2

    while r ≥ begin do
        A[w+1] ← gap
        A[w] ← A[r]
        r ← r − 1
        w ← w − 2