SIRALAMA ALGORİTMALARI Giriş ve Temel Kavramlar

“Belirli bir düzene göre yerleştirmek veya düzenlemek, sıraya koymak”, “Birbiri ardı sıra veya yan yana koyarak sıra durumuna getirmek”…  Sayısal ortamda ki bilgilerin(verilerin) bir anahtar bilgiye(veriye) göre sıralı erişilmesini sağlayan belli bir anlam kazanması için yapılan düzenlemedir. Yazılım ve donanım sistemlerinde sıralamanın önemi çok büyüktür. Sıralanmış bir veri sadeleştiği için işlemler kolaylaşır ve hızlanır. Günümüz teknolojisinde sadelik ve hız ne kadar önemli olduğunu her bilişimci çok iyi bilir.Çok sayıda sıralama algoritması vardır. Verinin büyüklüğü, sayısı, geliş sırası, veri modeli vb. özellikler hangi algoritmanın daha kullanılacağını belirler. Bu algoritmalar rastgele bir yerleşime sahip olan dağınık veri kümesinin düzenlenmesi işini gerçekleştirir.  Şimdi sıralama algoritmalarında kullanılan bazı kavramlardan bahsedelim.

Anahtar Sözcük (Keyword): Sıralama işleminin gerçekleştirilmesi için bir bilgi parçasına ihtiyacı vardır. Bu bilgi parçası bir sayısal veri, cümle, tarih, vb. olabileceği gibi tüm bunların biraraya gelmesinden de oluşabilir. Anahtar sözcükler genelde küçük ve sadedirler. Küçüklük ve sadelikleri aksi yönde değiştikçe algoritmaların sonuç üretmesi de zorlaşacak ve zaman alacaktır.

Harici Sıralama( External Sorting): Sıralanmak istenen veri eğer bir disk/disket/ usb/ cd ve harici bir saklama biriminde tutuluyor ise bu verinin sıralama işlemine harici sıralama denir.

Dahili Sıralama( internal Sorting): Sıralanmak istenen veri RAM gibi erişimi çok hızlı belleklerde tutuluyor ise bu verinin sıralama işlemine dahili sıralama denir.

Yukarıda tanımını yaptığım harici ve dahili sıralama, algoritmanın seçimini en çok etkileyen özelliklerden bir tanesidir. Harici sıralama işlemlerinde verilerin yer değişiminin az olmasını sağlayan algoritmalar seçilir. Çünkü harici depolama birimlerinde bu işlemler daha yavaş olacaktır. Kullanacağınız sıralama algoritması ne kadar hızlı olursa olsun çok fazla yer değişimi yapıyor ise yavaş işlem yapacağından olumlu sonuç alamayacaksınız. Dahili sıralama işlemlerinde ise verinin bellekte tutulamayacak kadar büyük olmaması gerekir.

İndexleme(indexed file structure): Dizinli dosya yapısı da denilebilir. Verilerin çok büyük olduğu kümelerde verileri sıralamakla uğraşılmaz. Bunun yerine her bir veriye tekil bir anahtar numarası verilir. Asıl verilerin yerleşimlerinde kesinlikle bir sıralama yapılmaz. Bunun yerine anahtar numaraları ve özellikleri kullanılarak sıralama yapılır. Özetle gerçek veriler harici/daha yavaş depolama birimlerinde sırası bir şekilde tutulurken anahtarları dahili yani bellekte sıralanırlar. Herhangi bir veriye ulaşılmak istendiğinde indexlenmiş anahtar kümesinden dosyanın yoluna ulaşılır ve dosya harici depolamadan kolaylıkla okunur.

Bir sıralama algoritması için iki adet çok önemli unsur bulunmaktadır.

• Yürütme Zamanı
• Gereken Bellek Alanı

Yürütme zamanı algoritmanın geliştirildiği kod parçası ve sıralama işleminin hangi fiziksel ortamda yapıldığına bağlıdır. Gerekli bellek alanı ise kullanılacak algoritma ile belli olur.

Şimdi arkadaşlar sıralama algoritmalarının zaman karmaşıklıklarını, uygulandığı veri modelini ve uygun olduğu bellek ortamını aşağıdaki tabloda paylaştım.

Sıralama Algoritması	Uygun Olduğu Bellek Ortamı	Veri Modeli	Karmaşıklık/En İyi	Karmaşıklık/Orta	Karmaşıklık/En Kötü
Selection Sort	Dahili, Harici	Bağlantılı Liste, Dizi	0.5*n²	0.5*n²	-
Quick Sort	Dahili	Dizi, Ağaç	0.5*n²	n*logn	-
Merge Sort	Dahili, Harici	Bağlantılı Liste, Liste, Dizi	3*n*logn	-	-
Insertion Sort	Dahili	Bağlantılı Liste, Dizi	0.5*n²	0.25*n²	-
Heap Sort	Dahili	Bağlantılı Liste, Liste	n*logn	3/4*(n*logn)	-
Bubble Sort	Dahili	Bağlantılı Liste, Dizi	-	-	n²