BİL207U-VERİ YAPILARI
Ünite 4: Sıralama Algoritmaları
Giriş
Bilgisayar endüstrisinin yaşamımıza girmesinden itibaren depolanan veriler üzerinde en çok sıralama ve arama işlemleri yapılır. Veri sıralamak için kullanılan temel algoritmalar, bu bölümde incelenecektir.
Sıralama Algoritması Nedir?
Sıralama; çok sayıda ögeyi büyükten küçüğe, küçükten büyüğe, uzundan kısaya, kısadan uzuna gibi ihtiyaca göre düzenleme işlemidir. Bilgisayar bilimlerinde programın ihtiyacına göre bu işlemleri yapan algoritmalar geliştirilmiştir. Sıralama algoritmaları, ögelerden oluşan liste verilerini girdi olarak alır. Bu listelere belirli işlemler uygular ve sıralı dizileri çıktı olarak verir.
Farklı amaçlar için kullanılan sıralama algoritmaları görünürde benzer işlemi yapsa da onları birbirinden ayıran en önemli fark performanslarıdır. Buradaki performans, algoritmanın çalışırken harcadığı kaynak ve sıralama yapılırken geçen süreyi ifade eder. Algoritmaların performansı veri boyutuyla doğrudan ilişkilidir. Küçük veriler için seçilecek algoritmanın performansı, geliştirici için çok önemli olmayabilir ancak veri sayısı büyüdüğünde algoritmanın sıralama işleminde kötü performans göstermesi, geliştirilen uygulamanın performansını düşürecektir.
Parabolik olarak performansı değişen uygulamalarda veri sayısı ve veri boyutu oldukça önemlidir. Günümüz bilgisayarları Ghz’ler seviyesinde işlem gücüne sahip olduğu için algoritmaların performansı az sayıda veriden oluşan listelerde (örneğin 1000 eleman gibi) mili saniyeler seviyesinde olacaktır ancak veri sayısı arttığında performans farklı saniyeleri hatta dakikaları bile bulabilir. Algoritma seçiminde, çalışılabilecek en büyük veri boyutu ve veri sayısı göz önüne alınmalıdır. Sıralama algoritmasında, ideal zaman karmaşıklığı değeri O(1) olmalıdır. Bunun için algoritmaya verilen verilerin sıralı olması ve algoritmanın veri setinde tek bir gezinmede sıralamayı sonlandırması gerekir.
Sıralama Algoritmaları İçin Test Kodu
Sıralama algoritmalarını incelemeye başlamadan önce algoritmaları test edeceğimiz sınıfı hazırlayacağız. Hazırladığımız kod; öge ekleme, ögelere erişim ve görüntüleme gibi işlemleri yapan bir dizi sınıfı olacak.
Sayfa 78'deki Kod 4.1'de dizi sınıfının yapısı verilmiştir. Bu kod bloğu çalıştırıldıktan sonra ekran çıktısı aynı sayfadaki Çıktı 4.1'deki gibi olacaktır.
Sıralama algoritmalarını incelemek için dizi elemanlarının rastgele üretilmiş verilerden oluşması ve algoritmaya sırasız olarak verilmesi gerekir. Algoritmanın ihtiyacı olan sayılar, rastgele sayı üreteçleri ile üretilir. Böylelikle algoritmalar her çalıştırmada farklı sayılarla test edilmiş olur.
Rastgele sayı dizisini oluşturmak için C# ile birlikte gelen Random sınıfı kullanılabilir. Random sınıfı ile sayı
oluştururken istenilen sayı aralığı için üst sınır bildirilebilir. Sayfa 79'daki Kod 4.2'de rastgele sayı dizisi üreten kod bloğu verilmiştir. Program çalıştırıldıktan sonra, oluşturulan dizi Çıktı 4.2'deki gibi rastgele sayılar içerecektir.
Ünite içerisinde incelenen tüm kodların birleştirilmiş hâli, ünite sonunda EK-1’de paylaşılmıştır.
Temel Sıralama Algoritmaları
Bilgisayar bilimlerinde yıllardır süregelen çalışmalarda birçok sıralama algoritması geliştirilmiştir. Bunlar içinde bazıları tasarlandıkları veri setlerinde performanslı çalışırken geri kalan veri setlerinde daha az başarılı olabilirler. Geliştirici, kullanacağı veri setine uygun algoritmayı seçebilir veya özel algoritmasını tasarlayarak performansı arttırabilir.
Kitabınızın bu ünitesinde, bilgisayar bilimlerinde yaygın olarak kullanılan sıralama algoritmaları incelenecektir. Temel sıralama algoritmaları, her veri seti için en iyi sonucu vermeseler de genel olarak performanslı algoritmalardır. Özellikle küçük veri setlerinde daha başarılı sıralamalar yapabilmektedirler.
Baloncuk Sıralama (Bubble Sort)
Baloncuk sıralama, listenin bir başından diğer başına kadar kayan bir baloncuk görüntüsü verdiği için bu şekilde adlandırılmıştır.
Listedeki rastgele verilen elemanları artan sıra ile sıralarsak baloncuk sağa doğru kayacaktır. Azalan sıra ile sıralarsak baloncuk sola doğru kayacaktır. Listedeki elemanları, ikili olarak yanındaki ile karşılaştırır ve sıralama yapılmak istenen yönde yer değiştirir. Artan sıralama yapılıyorsa büyük olan eleman sağ tarafa, küçük eleman sol tarafa alınarak yerleştirme yapılır.
Çıktı 4.2’de elde edilen değerler Baloncuk Sıralama için sayfa 80'deki Tablo 4.1’de örnek olarak kullanılmıştır. Tablo incelendiğinde en büyük elemanın 96 ögesi olduğu görülecektir. Bu eleman en büyük eleman olduğu için soldan sağa kadar sıra ile tüm diğer ögelerle karşılaştırılmıştır. Algoritmanın ilk baloncuk değeri 96’dır. Algoritma tüm elemanları sıralayana kadar çalışmaya devam edecektir. n elemanlı bir dizide, n tekrar yaparak sonuç bulunabilir.
Baloncuk sıralaması algoritmasının C# kodu 80. sayfada verilen Kod 4.3'teki gibidir. Burada verilen kod bloğunu incelediğinizde yer değiştirme işleminin yapılış yöntemini fark etmişsinizdir. if bloğunda, elemanların büyük küçük olma durumuna göre değişiklik yapılmasına karar verilmektedir. Yer değiştirilecek elemanlardan ilki, temp isimli değişkende depolanmaktadır. Diğer eleman temp içerisine alınan elemanın yerine yerleştirilmektedir. Daha sonra temp içerisindeki eleman yeni yerine taşınmaktadır.
İç ve dış döngüler tamamlanana kadar program algoritma çalışmaya devam eder.
Seçerek Sıralama (Selection Sort)
İnceleyeceğimiz diğer temel sıralama algoritması Seçerek Sıralama algoritmasıdır. Çalışma esnasında dizi aralığındaki en küçük elemanı seçerek çalıştığı için bu isim verilmiştir.
Algoritma, sıralanacak diziyi baştan itibaren tarar. Bulduğu en küçük elemanı seçer ve dizinin 0 no’lu indeksindeki eleman ile yer değiştirir. İlk adım tamamlanmış olur. İkinci adımda, dizinin 1 no’lu indeksinden itibaren son elemana kadar tarar ve en küçük elemanı tekrar seçer. Seçilen en küçük elemanın 1 no’lu indekste bulunan elemanla yer değiştirilmesi yapıldıktan sonra 2. adım tamamlanır. n elemana sahip dizide n tekrar yapılarak işlem tamamlanır.
Seçerek sıralama algoritmasında iki döngü kullanılır. Dış döngü, dizideki ilk ögeden bir sonraki son ögeye doğru hareket ederken iç döngü dizinin ikinci ögesinden son ögeye doğru hareket eder. Algoritma, mevcut adıma ait başlangıç ögesinden küçük ögeleri arar. İç döngünün her yinelemesinden sonra dizideki en küçük değer dizideki uygun yerine atanır.
Sayfa 81'deki Kod 4.7'deki kod bloğunda Seçerek Sıralama algoritması için C# kodu verilmiştir. Kod yapısı incelendiğinde iç içe iki adet for döngüsü vardır. Algoritmanın BigO nostasyonunun n2 olduğu görülecektir.
Çıktı 4.2’de elde edilen değerler, 82. sayfadaki Tablo 5.2’de algoritmanın çalışmasını incelemek için sıralanmıştır. Çalışma adımları incelendiğinde 1. adımda 96 ve 14 değerlerine sahip ögeler yer değiştirmiştir. 2. adımda ise 15 değerine sahip öge en küçük eleman olduğu için değiştirilecek öge bulunamamış ve olduğu gibi bırakılmıştır. Diğer adımlarda incelendiğinde algoritmanın 7. adımdan sonra veriler üzerinde bir değişiklik yapmadığı görülecektir. Veriler istenilen sıraya gelmiş olsa bile algoritma çalışmaya devam edecektir.
Ekleme Sıralama (Insertion Sort)
Temel sıralama algoritmalarından bir diğeri ise Ekleme Sıralama (Insertion Sort) algoritmasıdır. Bu algoritmaya örnek olarak kitaplığına kitapların yerleştirilmesi düşünülebilir. Rastgele dizi hâlinde bulunan kitaplar, sol taraftan başlanarak düzenlenebilir. Her adımda sıradaki kitap önceki kitaplar arasındaki yerine eklenir ve sıradaki kitap alınır. Çıktı 4.2’de verilen sayıların ekleme sıralama algoritması ile sıralanması 82. sayfadaki Tablo 4.3’te verilmiştir.
Tablo 4.3 incelendiğinde algoritma ilk adımda 96 ögesini sabit olarak almıştır. Bir sonraki eleman olan 15’i ekleyecek konumu belirleyecektir. 15 ögesi 96 ögesinden küçük olduğu için 96’nın soluna eklemiştir. 2. Adımda düzenlenmiş ögeler 15 ve 96’dır. Sıradaki 66 ögesi, 15 ve 96 ögelerinin arasına eklenecektir. Algoritma, sıradaki tüm düzenlenmemiş ögeleri, düzenlenmiş ögelerin arasına ekleyerek çalışmasını tamamlayacaktır. Çalışma adımları incelendiğinde bu algoritmanın önceki algoritmalar gibi
ögeleri değiştirerek değil, yeni gelen ögeyi dizi içerisindeki yerine ekleyerek çalıştığı görülecektir.
83. sayfadaki Kod 4.8’de ekleme sıralama algoritması için yazılan C# kodunu inceleyebilirsiniz.
Ekleme sıralama algoritması, iki adet döngü içerir. İlk döngü dizi elemanları üzerinde teker teker gezerken ikinci döngü sıradaki elemanı, önceki adımlarda düzenlenmiş olan elemanlar arasında olması gereken yere yerleştirir.
Hızlı Sıralama (Quick Sort)
Diğer algoritmalara nazaran daha performanslı olan bu algoritma, dikkatli kodlama yapılmadığı takdirde işlem yükü olarak daha maliyetli çalışır.
Dizi elemanlarından biri pivot değer olarak seçilerek algoritma başlatılır. Pivot, baştaki eleman seçilebileceği gibi rastgele bir elemanda seçilebilir. Pivotun dizi elemanlarına uygun seçilmesi algoritma başarısını etkileyecektir. Pivot seçildikten sonra dizinin diğer elemanları, pivottan küçük veya büyük olmasına göre iki gruba ayrılır. Sonraki adımda, bu iki grup kendi içlerinde tekrar bölünerek sıralanır. Grupların sıralaması için sıralama algoritması özyinelemeli (recursive) olarak çalıştırılır.
Çıktı 4.2’de elde edilen rastgele sıralı elemanların hızlı sıralama algoritmasında yeniden sıralanmasını gösteren adımlar 84. sayfadaki Tablo 4.4’te verilmiştir.
Tablo 4.4 incelendiği zaman listenin en sağındaki elemanın pivot alınarak sıralama yapıldığı görülecektir.
Başlangıç adımında pivot değeri 14 seçilmiştir. 1. adım sonunda, pivot değerinden küçük eleman olmadığı için yalnızca büyük elemanlar ile grup oluşturulmuştur. Listelenecek yeni grup 15, 66, 90, 35, 94, 71, 61, 34, 96 elemanlarından oluşmaktadır. Yeni pivot değeri 96 olarak seçilecektir.
2. Adımda pivot değeri listenin en sağında olan 96 seçilmiştir. 96 aynı zamanda en büyük eleman olduğu için liste sıralamasında değişiklik yapılmadan geçilmiştir. Pivot çıkartıldıktan sonraki elemanlardan oluşan liste (15, 66, 90, 35, 94, 71, 61, 34) sonraki adım için yeni grubumuz olacaktır. Bu grupta pivot 34 olarak seçilir.
3. Adımda pivottan küçük sadece bir eleman (15) vardır. Bu yüzden pivotun sol tarafında yine bir grup olmayacaktır. Sağ tarafta ise diğer elemanlar (90, 35, 94, 71, 61, 66) yeni bir grup oluşturacaktır. Bu grubun pivotu ise 66 olacaktır.
4. Adımda pivotun sol (35,61) ve sağında (71, 90, 94) iki grup oluşacaktır. Bu grupların en sağındaki elemanlar pivot olarak seçilecektir.
5. Adımda bir önceki adımdan gelen alt grubun dizilimi tamamlanmış ve yer değişikliğine gerek görülmemiştir. Üst grupta ise dizilim tamamlanmasına rağmen 2’den fazla eleman olduğu için yeni grup oluşacaktır. Bu grubun pivottan sonraki elemanları (71, 90) bir sonraki adıma yeni grup olarak taşınır. Pivot değeri ise 90 olacaktır.
6. Adımda listenin dizilimi tamamlanmış yeni bir alt grup oluşturmaya gerek kalmamıştır.
Tablo 4.4’ü incelediğinizde dizilimin 4. adımda tamamlandığını göreceksiniz. Kod içerisine adımlar arasında dizilimi kontrol edecek geliştirmeler yapıldığında algoritma performansının arttığını görebilirsiniz. Tabloya elemanları yerleştiren algoritma, 85. sayfadaki Kod 4.9’da verilmiştir. Algoritmaya ait bu kodlara birçok kaynakta rastlayabilirsiniz.
Hızlı sıralama algoritmasının bu ünitede incelenen diğer algoritmalara nazaran biraz daha karmaşık olduğunu fark etmişsinizdir ancak algoritmanın performansını incelediğinizde bu karmaşıklığın göz ardı edilebileceğini fark edeceksiniz. Kod 4.9 incelendiğinde algoritmanın zaman karmaşıklığı, en kötü durumda O(n2), ortalama
durumda ise O(n.log(n)) olduğu görülecektir. Hızlı sıralama ve diğer algoritmaların performansı bir sonraki konuda çalışma süreleri ile incelenecektir.
Sıralama Algoritmalarının Zaman Karşılaştırmaları
İncelediğimiz dört farklı sıralama algoritmasının çalışma sürelerini bu konu altında karşılaştıracağız. Çalışma sürelerini incelemek için algoritmayı eleman sayılarını 1000 ve 10000 seçerek iki defa çalıştırıyoruz. Algoritmaların çalışma sürelerini gözlemlemek için Timing sınıfını kullanacağız. Bu sayede algoritmaların çalışmaları arasındaki farkı gözlemleyebileceğiz.
Algoritmaları test etmek için kullanacağımız kodu 86. sayfadaki Kod 4.10’da inceleyebilirsiniz.
Tüm algoritmaları 1000 elemanla test ettikten sonra konsol ekranında sayfa 87'deki Çıktı 4.3’teki görüntüyü görebilirsiniz.
Ekranda çıktılar incelendiğinde Hızlı Sıralama algoritmasının çalışma süresi, diğer algoritmalara göre oldukça azdır. Eleman sayıları 10000 yapılarak incelendiğinde çalışma süreleri arasındaki fark daha iyi gözlemlenebilecektir.
Eleman sayıları ilk teste göre 10 katına çıkarıldı. Baloncuk, Seçerek ve Ekleme Sıralama algoritmalarının BigO notasyonları O(n2) olduğu için çalışma süreleri de eleman
sayısına bağlı olarak yaklaşık 100 katına çıktı ancak BigO notasyonu O(nlogn) olan Hızlı Sıralama algoritmasının çalışma süresi yaklaşık 5 kat arttı. Bu ünitede incelenen algoritmaların BigO notasyonları 87. sayfadaki Tablo 4.5’te verilmiştir.