Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen
bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan
sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama
işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için
sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için
önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini
ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar.
Sıralama algoritmaları,
tanımı çok yalın olmasına karşın çözümü çok karmaşık olan bir işi gerçekleştirdikleri
için, üzerinde en fazla araştırma yapılan bilgisayar bilimi konularından biridir.
Çoğu kişi sıralama sorununu çözülmüş bir sorun olarak görse de, yeni sıralama algoritmaları
üzerinde araştırmalar sürmektedir. Örneğin kütüphane sıralaması ilk olarak 2004
yılında ortaya atılmıştır. Sıralama algoritmaları, sayılarının çok olması ve değişik
yaklaşımlar sunmaları nedeniyle özellikle giriş düzeyindeki bilgisayar bilimleri
derslerinde büyük O gösterimi ve veri yapıları gibi temel algoritma kavramlarının
açıklanması amacıyla yaygın biçimde kullanılırlar.
Bilgisayar bilimlerinde kullanılan sıralama algoritmaları genellikle aşağıdaki ölçütlere
göre sınıflandırılır:
- Hesaplama karmaşıklığı: Dizideki öğelerin karşılaştırılmasının
en iyi, ortalama ve en kötü başarımının dizinin boyutu (n) cinsinden gösterilmiş
halidir. Olağan uygulamalarda sıralama algoritmalarının iyi durum başarımı O(n log
n) ve kötü durum başarımı is ?(n²)'dir. Bir sıralama algoritmasının istenen karmaşıklığı
O(n)'dir. Yalnızca soyut bir anahtar karşılaştırması yapan bütün sıralama algoritmaları
en kötü durumda her zaman ?(n log n) karşılaştırma yaparlar.
- Yer Değiştirme Karmaşıklığı (yerinde sıralama algoritmaları için).
- Bellek (ve diğer donanım kaynaklarının) Kullanımı: Bazı sıralama
algoritmaları dizinin içerdiği öğelerin dizinin saklandığı alanda sıralar. Böylece
sıralanan öğeler dışında yalnızca O(1) ya da O(log n)'lik bir ek bellek alanı gerekir.
Bazı algoritmalar ise verinin geçici olarak saklanması için dizinin tutulduğu alanın
dışında ek bellek alanlarına gereksinim duyar.
- Özyineleme: Bazı algoritmalar ya özyinelemeli ya da özyinelemesiz
çalışırken, birleştirmeli sıralama gibi bazı algoritmalar iki biçimde de uygulanabilir
- Kararlılık: Kararlı sıralama algoritmaları sıralanacak dizinin
içinde değerleri birbirine eşit olan öğerlerin birbirlerine göre olan konulmlarını
korur. Başka bir deyişle, bir sıralama algoritması kararlı olduğunda, eğer R
ve S gibi içerdiği değer aynı olan iki öğe bulunduran asıl dizide, R,
S' den önce geliyorsa, sıralanmış dizide de R, S'den önce gelir.
Dizinin içinde birbirine eşit değerler içeren öğeler birbirlerinden ayırt edilemiyorsa
(örneğin sayılar ya da harfler gibi değerler öğenin kendisini oluşturuyor ise) kararlılık
bir sorun değildir. Ancak aşağıda gösterildiği gibi sayı çiftleri, her çiftin virgülden
önceki sayısına göre sıralanacağı düşünülürse kararlılık sorunu çıkar.
(4, 1) (3, 7) (3, 1) (5, 6)
Bu durumda, 2 değişik sonuç mümkündür; ilk çözüm sıralama anahtarlarının değerleri
aynı olan öğelerinin sırasını korur, ikincisi ise korumaz:
(3, 7) (3, 1) (4, 1) (5, 6) (sıra korunmuş)
(3, 1) (3, 7) (4, 1) (5, 6) (sıra değişmiş)
Kararsız sıralama algoritmaları sıralama anahtarlarının değerleri aynı olan
öğelerin dizi içindeki sırasını değiştirebilir ancak kararlı sıralama algoritmaları
asla değiştirmez. Kararsız sıralama algoritmaları özellikle kararlı olacak biçimde
uygulanabilir. Bunu yapmanın bir yolu yapay olarak anahtar karşılaştırmasını anahtlarının
değerleri birbirine eşit olan iki öğenin durumunu belirlemek için asıl listedeki
konumlarını ölçüt olarak kullanacak biçimde genişlmetmektir. Ancak asıl dizideki
öğre sırasının hatırlanması çoğu zaman ek saklama alanı gerektirir.
- Kaşılaştırma sıralaması olup olmama:
Bir karşılaştırma sıralaması sıralanacak veriyi, bir karşılaştırma işlemi kullanarak,
karşılaştırarak inceler.
- Genel Yöntem: Araya sokma, değiştirme, seçme, birleştirme vb. Değiştirme sıralamalarına
kabarcık sıralaması ve hızlı sıralama örnek olarak gösterilebilir. Yığın sıralaması
ise seçme sıralamalarındandır.
Sıralama Algoritmaları Çeşitleri:
- Karşılaştırma ile Sıralayan Sıralama Algoritmaları
Kabarcık Sıralaması, Kokteyl Sıralaması, Tarak Sıralaması, Cüce Sıralaması,
Seçmeli Sıralama, Eklemeli Sıralama, Kabuk Sıralaması, Ağaç Sıralaması, Kütüphane
Sıralaması, Birleştirmeli Sıralama, Yerinde Birleştirmeli Sıralama, Yığın Sıralaması,
Rahat Sıralama, Hızlı Sıralama, İçgözlemle Sıralama,
Sabır Sıralaması, İplik Sıralaması.
- Karşılaştırmadan Sıralayan
Sıralama Algoritmaları
Güvercin Yuvası Sıralaması, Kova Sıralaması, Sayarak Sıralama, En anlamsız
Basamağa göre sıralama, En anlamlı Basamağa göre sıralama, Spreadsort.
- Verimsiz Sıralama Algoritmaları
Saçma sıralama, Rastgele değiştirmeli sıralama, Stooge sort, Bead sort, Simple
pancake sort, Sorting networks.
