Sıralama Algoritmaları (Sorting Algorithms)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde verilmiş olan bir grup sayının küçükten büyüğe (veya tersi) sıralanması işlemini yapan algoritmalara verilen isimdir. Örneğin aşağıdaki düzensiz sayıları ele alalım:

5 9 2 3 7 11 -4 6

Bu sayıların sıralanmış hali

-4 2 3 5 6 7 11

olacaktır. Bu sıralama işlemini yapmanın çok farklı yolları vardır ancak bilgisayar mühendisliğinin temel olarak üzerine oturduğu iki performans kriteri buradaki sonuçları değerlendirmede önemli rol oynar.

  • Hafıza verimliliği (memory efficiency)
  • Zaman verimliliği (Time efficiency)

Temel olarak algoritma analizindeki iki önemli kriter bunlardır. Bir algoritmanın hızlı çalışması demek daha çok hafızaya ihtiyaç duyması demektir. Tersi durumda da bir algoritmanın daha az yere ihtiyaç duyması daha yavaş çalışması demektir. Ancak bir algoritma hem zaman hem de hafıza olarak verimliyse bu durumda diğer algoritmalardan başarılı sayılabilir.

Genellikle verinin hafızada saklanması sırasında veriyi tutan bir berlirleyici özelliğinin olması istenir. Veritabanı teorisinde birincil anahtar (primary key) ismi de verilen bu özellik kullanılarak hafızada bulunan veriye erişilebilir. Bu erişme sırasında şayet berlileyici alan sıralı ise erişimin logaritmik zamanda olması mümkündür. Şayet veri sıralı değilse erişim süresi doğrusal (linear) zamanda olmaktadır.

Aşağıda bazı sıralama algoritmaları verilmiştir:

Yukarıda verilen veya herhangi başka bir sıralama algoritması genelde küçükten büyüğe doğru (ascending) sıralama yapar. Ancak bunun tam tersine çevirmek (descending) genelde algoritma için oldukça basittir. Yapılması gereken çoğu zaman sadece kontrol işleminin yönünü değiştirmektir.

Ayrıca sıralama işleminin yapılması sırasında hafızanın kullanımına göre de sıralama algoritmaları :

şeklinde iki grupta incelenebilir.

Algoritmaların karşılaştırılması için aşağıdaki tablo hazırlanmıştır:

Algoritma İngilizcesi Algoritma Analizi Kararlılı Yöntem Açıklama

 
En İyi Ortalama En Kötü
Seçerek Sıralama Selection Sort n2 n2 n2 Kararsız Seçerek
Hızlı Sıralama Quick Sort n log(n) n log(n) n2 Kararsız Parçala Fethet
Birleştirme Sıralaması Merge Srot n log(n) n log(n) n log(n) Kararlı Parçala Fethet
Yığınlama Sıralaması Heap Sort n log(n) n log(n) n log(n) Kararsız Seçerek
Sayarak Sıralama Counting Sort n + 2k n + 2k n + 2k Kararsız Sayarak k ikinci dizinin boyutu.
Kabarcık Sıralaması Bubble Sort n n2 n2 Kararlı Yer Değiştirme
Kokteyl Sıralması Coctail Sort n n2 n2 Kararlı Yer Değiştirme Çift Yönlü kabarcık sıralaması (bidirectional bubble sort) olarak da bilinir ve dizinin iki ucundan işleyen kabacrık sıralamasıdır.
Taban Sıralaması Radix Sort  n(k/t)  n(k/t)  n(k/t) Kararlı Gruplama / Sayma k, en büyük eleman değeri, t ise tabandır
Sokma Sıralaması Insertion Sort  n d+n n2 Kararlı Sokma d yer değiştirme sayısıdır ve n2 cinsindendir
Sallama Sıralaması Shaker Sort  n2 n2 n2 Kararsız Seçme Çift yönlü seçme sıralaması (bidirectional selection sort) olarak da bilinir.
Kabuk Sıralaması Shell Sort  n3/2 n3/2 n3/2 Kararsız  Sokma
Rastgele Sıralama Bogo Sort  1  n n!  sonsuz Kararsız  Rastgele Algoritma olduğu tartışmalıdır. Knuth karıştırması (knuth shuffle) süresinde sonuca ulaşması beklenir.
Bozo Sıralaması Bozo Sort 1 n! sonsuz Kararsız Rastgele Rastegele sıralamanın özel bir halidir. Rastgele olarak diziyi karıştırdıktan sonra, dizi sıralanmamışsa, yine rastgele iki sayının yeri değiştirilip denenir.
Goro Sıralaması Goro Sort 2(log(d) / log(2)) 2(log(d) / log(2)) 2(log(d) / log(2)) Kararsız Rastgele 2011 Google kod yarışı (google code jam) sırasında ortaya çıkmıştır. Sıralanana kadar her alt küme permüte edilir. Buradaki performans değeri ispatlanmamıştır ve d dereceyi ifade eder.
Şanslı Sıralama Lucky Sort  1  1  1  Kararsız  Rastgele  Algoritma olarak kabul edilmemelidir.
Serseri Sıralama Stooge Sort  ne ne ne  Kararsız  Yer değiştirme  e, doğal logairtma sayısıdır (2,71)
Şimşek Sıralaması Partial Flash Sort  n  n + d  n + d  Kararsız  Yer Değiştirme  d, kullanılan ikinci algoritmanın performansıdır, bu algoritma bu listedekilerden herhangi birisi olabilir.
Permütasyon Sıralması Perm Sort n n n! n n! Kararsız Yer Değiştirme
Bazı Yegane Sıralaması Several Unique Sort n n2 n2 Kararsız Yer Değiştirme Bir bilgisayar programı tarafından bulunmuştur.
Tarak Sıralaması Comb Sort n log(n) n log(n) n log(n) Kararsız Yer Değiştirme Kabarcık ve hızlı sıralama algoritmalarının birleşimi şeklinde düşünülebilir

 

Yukarıdaki yazıda geçen kararlılık kolonu ile, bir algoritmanın bitiş kontrolüne dayanmaktadır. Örneğin sıralı bir dizi verilse bile sıralama işlemi yapmaya çalışır mı?

Yukarıdaki tabloda bulunan algoritma analizi bilgisi için aşağıdaki yazıları okumanızda yarar olabilir:

Yorumlar

  1. Reply
    Sümeyra

    yeni almaya başladığımız veri tabanı dersimiz için gerekli olan araştırmada, sıralama algoritmaları ile ilgili bilgi edinmemde anlatımınızdan yararlandım teşekkür ederim..

  3. Reply
    sahin

    merhaba hocam, internette tournament sort ile ilgili türkçe kaynak pek yok, burada sitenizde de göremedim, tournament sort u da eklerseniz çok makbule geçer
    teşekkürler

  5. Reply
    Can DOĞRU

    elleriniz dert görmesin algoritma dersinden sıralama algoritmaları çeşitlerini araştırmam gerekiyordu çok iyi oldu.

  6. Reply
    Samet

    İplik Sıralama java kodu lazım yardımcı olursanız sevnirim vikipedide buldum ama sağlam diil çalışmıo

  8. Reply
    Hanife

    Merhaba Hocam,
    Ellerinize sağlık. Makaleleriniz oldukça yararlı.
    Size bir sorum olacak.
    Elimde double sayılardan oluşan bir dizi var.
    Bunların sıralamasını nasıl yapabilirim.
    integer sayılarda kullanılan yöntemlerle bu işlemi gerçekleştiremedim.

  9. Reply
    Şadi Evren ŞEKER Article Author

    sayıların tipinin farklı olması sıralama algoritmasını etkilemez, aynı algoritmaları kullanabilirsiniz (birkaçı hariç).
    Hangi algoritmayı deniyorsanız, kodunuzu yazın, hatanızı bulup düzeltmeye çalışayım.

  10. Reply
    Utku

    Türkçe olmakla beraber içeriği bol ve anlatım güzel olan sayılı sitelerden birisi, basit ve etkili anlatımlarla öğrenmeyi kolaylaştıran bir sayfa içten teşekkür ediyorum.

Bir cevap yazın

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