Önceki sayımızda bilgisayar biliminin en temel kavramlarından biri olan algoritmalar hakkında genel bilgi verilmişti. Bu sayımızda ise biraz daha detaya girip, algoritma çeşitlerinin en önemlilerinden biri olan sıralama algoritmalarını(sorting algorithms) ele alacağız.
Sıralama algoritmalarını kullanmamızdaki amaç, -algoritmanın isminden de anlaşılacağı üzere- sahip olduğumuz veriyi en hızlı şekilde büyükten küçüğe (ya da küçükten büyüğe) bir sıraya sokmak. Bunun için kullanılan bir çok sıralama algoritması mevcut. Bazısı çok hızlı ama yazımı zor, bazısı az sayıda veri için çok hızlı, bazısının da yazması kolay. Bu yazımızda, en populer sıralama algoritmaları ile ilgili bilgiler vermeye çalışacağız.
Elemeli Sıralama(Bubble Sort)
Sıralama algoritmaları arasında en yavaş çalışanıdır. Aslında bilgisayar bilimi eğitiminde, sıralama algoritması hakkında bir temel oluşturulması için öğretilmesi dışında pek kullanılmaz. Elemeli sıralamada yapılan kısaca şöyledir:
Veri setinin ilk iki elemanı okunup karşılaştırılır. İlk veri ikinciden küçükse, ikinci ve üçüncü veri karşılaştırılır; büyükse ikisi yer değiştirir. Bu işlemler son veriye ulaşana kadar devam eder ve doğru sıralamaya ulaşana kadar tekrar baştan başlar. Örnek verelim:
( 5 1 4 2 8 ) --> ( 1 5 4 2 8 ) : burda, ilk iki veri karşılaştırılıyor ve ikinci küçük olduğu için yer değiştiriyorlar.
( 1 5 4 2 8 ) --> ( 1 4 5 2 8 )
( 1 4 5 2 8 ) --> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) --> ( 1 4 2 5 8 ) : son elemana ulaşılıyor ama setimiz hala sıralı değil, o yüzden tekrar baştan başlıyoruz.
( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) --> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )
Seçmeli sıralama (selection sort)
Basit ve yazması kolaydır. Ama elemeli sıralamaya göre daha iyi olsa da, diğer algoritmalara göre yine yavaş çalışır. Seçmeli sıralamada yapılan kısaca şöyledir: Veri seti sırayla okunur ve en küçük olan eleman, setimizin ilk elemanıyla yer değiştirir. İkinci elemandan itibaren set bir daha okunur ve en küçük veriyle ikinci veri yer değiştirir. Bu işlem son veriye gelene kadar devam eder. Örnek verelim:
31 25 12 22 11 : veri setimiz
11 25 12 22 31 : en küçükleri olan 11, ilk sıradaki veri ile yer değiştirdi.
11 12 25 22 31
11 12 22 25 31
Eklemeli sıralama(Insertion Sort)
Elemeli sıralamaya göre daha hızlı olan bu sıralama, küçük setler için daha uygundur. Seçmeli sıralamaya benzer ama ona oranla daha hızlıdır. Bu sıralama iki şekilde yapılabilir. Birincisi, bundan önce anlattığımız sıralamalarda olduğu gibi, aynı set içerisinde sıralama, diğer yöntem ise, fazladan bir boş set daha kullanılarak yapılan sıralama. İkinci yöntemde fazladan set ve dolayısıyla fazladan hafıza kullanıldığı için, ilk yöntem daha çok tercih edilir. Eklemeli sıralamada yapılan işlem kısaca şöyledir:
Veriler sırayla okunur ve kendinden önceki verilerle kıyaslanıp en uygun yere konur. Bu algoritmayı yerden sırayla çektiğimiz iskambil kartlarını sıralamamıza benzetebiliriz. Örnek verelim:
34 8 64 51 32 21 : ilk listemiz
8 34 64 51 32 21 :8 , 34 ün önüne eklendi.
8 34 64 51 32 21 :64, kendisinden önceki rakamlardan büyük olduğu için yerinde kaldı.
8 34 51 64 32 21
8 32 34 51 64 21
8 21 32 34 51 64
Birleştirmeli Sıralama (Merge sort)
Böl ve işgal et (divide and conquer) stratejisi kullanılır. Bu sıralama algoritmasında, fazladan hafıza kullanılır. Yukarıda bahsettiğimiz algoritmalara göre çok daha hızlıdır. Yapılan işlem kısaca şöyledir:
Setimiz, iki veri kalana kadar parçalara ayrılır (sürekli yarıya bölünerek) ve her ikili parça kendi içinde sıralanır. Her iki parça sıralandıkça, diğer ikili parçayla kıyaslanıp sıralanır ve böylece elimizde sıralı veri dizisi oluşur. Örnek verelim:
Çabuk Sıralama (Quick Sort)
Birleştirmeli sıralama algoritmasında olduğu gibi, çabuk sıralama algoritması da böl ve işgal et (divide and conquer) stratejisini kullanır. Çabuk sıralama performans olarak diğer sıralamalara göre çok iyidir. Özellikle büyük boyutlu setlerde bu algoritmayı kullanmak çok önemlidir. Fakat çabuk sıralama algoritmasını koda dökebilmek zordur. Bu yüzden, sıralamaya ihtiyaç duyan kişi, bu algoritmayı yazmak için harcayacağı zamanın, sıralama yaparken kazanacağı zamana oranını iyi hesaplaması gerekir. Çabuk sıralamada yapılan işlem kısaca şöyledir:
Veri setimiz iki parçaya ayrılır, bu işlem için bir veri pivot olarak seçilir, kalan iki parça ise, pivottan küçükler ve pivottan büyüklerin oluşturduğu parçalar olur. Bu iki parçaya da yine çabuk sıralama algoritması uygulanır. Yani çabuk sıralama algoritması, kendi içerisinde yine kendini çağırır (özyineleme - recursion). Örnek verelim:
27 63 1 72 64 58 14 9 : Pivot 9 olsun.
1 9 63 72 64 58 14 27 : 9 dan küçükler 9 un soluna, büyükler sağına yerleştirildi. Sağ taraftaki set için pivot 27 olsun.
1 9 14 27 64 58 72 63 : 27 den küçükler 27 nin soluna, büyükler sağına yerleştirildi.
1 9 14 27 58 63 72 64
1 9 14 27 58 63 64 72
En yaygın olan beş algoritmayı sizlerle paylaştık. Gördüğünüz gibi sıralama işlemi için kullanılacak algoritmayı seçmek için; hız mı, bellek kullanımı mı yoksa sıralama programını yazmanın kolaylığının mı önemli olduğuna karar vermek çok önemli.