Sıralama Algoritmaları – II

Neslihan Şirin Saygılı —  2 Nisan 2015 — Yorum bırakın

Sıralama algoritmalarının ilk kısmını içeren yazımda basit sıralama algoritmaları olarak Seçmeli (Selection sort) ve Eklemeli (Insertion sort) sıralama algoritmalarından bahsetmiştim. Bu yazıda gelişmiş sıralama algoritmaları olarak Birleştirmeli (Mergesort) ve Hızlı (Quicksort) sıralama algoitmalarını inceleyeceğim. Bu algoritmaları gerçeklerken hem birleştirme (merge) ve bölümleme (partition) gibi işlemler, hem de özyineleme (recursion) yaklaşımını kullanmış olacağız.

Gelişmiş sıralama algoritmaları

Gelişmiş sıralama algoritmaları hem başarımı yüksek, hem de genel yaklaşım olarak daha akıllıca yöntemler içeren algoritmalardır. Birleştirmeli Sıralama ve Hızlı Sıralama algoitmaları böl ve yönet yaklaşımının güzel birer örnekleridir. Öte yandan zaman karmaşıklıkları göz önünde bulundurulunca daha yüksek başarım, yani daha düşük karmaşıklıkla çalışırlar.

1. Birleştirmeli Sıralama

Birleştirmeli sıralama, adını sıralanmış iki diziyi birleştirerek (merge) sıralanmış bir dizi haline getirmesinden alır. Birleştirmeli sıralama, diziyi iki eşit parçaya ayırıp bu yarı dizileri kendi içinde özyinelemeli olarak sıralar ve sıralanmış dizileri birleştirir. Diziyi iki parçaya ayırıp bu parçalar üzerinde işlem yapan birleştirmeli sıralama, böl ve yönet algoritmalarının güzel bir örneğidir. Algoritmanın olumsuz bir yönü N elemanlı diziyi birleştirmek için N elemanlı ek bir dizi kullanmasıdır. Algoritmanın çalışma şeması aşağıdaki gibidir.

Merge-sort-example-300px

Algoritmanın Java dilindeki örnek kodunu aşağıda görebilirsiniz.

Birleştirmeli sıralamanın karmaşıklığını hesaplamak için, özyinelemeli yaklaşıma uyan şekilde sıralanacak diziyi bir ağaç yapısına taşıyalım. Algoritma her adımda diziyi ikiye bölüp en küçük birime geldiğinde sıralayıp daha sonra sıralanmış alt dizileri birleştirerek sonuca varır. Bu diziyi Birleştirmeli sıralamaya uygun şekilde ağaç yapısına yerleştirince her bir düğüm bir alt diziyi temsil eder. Ağaç tam olarak n seviye içerir. k sayısı 0’dan n-1’e kadar ağaç seviyesini temsil etsin, yukarıdan aşağıya doğru ağacın k. seviyesinde 2k tane düğüm bulunur. Bu düğümlerin her biri 2(n-k) uzunluğunda bir alt diziyi temsil eder. Bir alt dizinin eleman sayısı 2(n-k) olduğu için en fazla 2(n-k) karşılaştırma yapılabilir. Ağacın her seviyesindeki alt dizi sayısı ve yapılabilecek en fazla karşılaştırma sayısı
2k * 2(n-k) = 2n‘dir.
n seviye ağaç için toplam n* 2n karşılaştırma yapılır.
Elde edilen n* 2n değerinin asimptotik üst sınırı O(NlgN) değeridir.
*Birleştirmeli sıralama her durumda O(nlogn) karmaşıklığında çalışacağını garanti eder.

2. Hızlı Sıralama

Hızlı sıralama, sıralanacak diziyi seçilen pivot elemana göre bölümlendirir (partition) ve bu bölümleri kendi içlerinde özyinelemeli olarak sıralar. Yine hızlı sıralama da böl ve yönet yaklaşımına güzel bir örnektir. Hızlı sıralama, kolay uygulanabilmesi, çeşitli veri tipleriyle çalıştırılabilmesi ve genel olarak hızlı çalışması sebebiyle oldukça yaygın kullanılan ünlü bir sıralama algoritmasıdır. Ortalama O(NlogN) başarımı göstermesi ve Birleştirmeli sıralamanın aksine ek alana ihtiyaç duymaması incelediğimiz dört algoritmanın içerisinde birinciliği Hızlı Sıralama’ya vermemiz için yeterlidir. Algoritmanın çalışma şeması aşağıdaki gibidir.

Quicksort-example

Algoritmanın Java dilindeki örnek kodunu aşağıda görebilirsiniz.

Değerlendirme

Genel olarak basit ve gelişmiş sıralama algoritmalarını karşılaştırırsak, incelediğimiz basit sıralama algoritmaları ortalama O(N2) karmaşıklığıyla çalışıyorlarken, gelişmiş sıralama algoritmaları böl ve yönet yaklaşımına uygun özyinelemeli olarak gerçekleştirilen (daha akıllıca) ve ortalama O(NlogN) karmaşıklığıyla çalışan hızlı algoritmalardır. Aşağıda incelediğimiz dört algoritmanın zaman ve alan karmaşıklıkları karşılaştırmalı olarak gösterilmiştir.

Sıralama algoritmalarının zaman ve alan karmaşıklık değerlendirmesi.

Sıralama algoritmalarının zaman ve alan karmaşıklık değerlendirmesi.

Kaynaklar
1. Robert Sedgewick, Kevin Wayne, Algorithms 4th Edition, Addison-Wesley 2011 (chapter 2 p. 270-301).
2. http://www.sorting-algorithms.com/, en son 26.03.2015 tarihinde erişildi.
3. https://en.wikipedia.org/wiki/Merge_sort, en son 26.03.2015 tarihinde erişildi.
4. https://en.wikipedia.org/wiki/Quicksort, en son 26.03.2015 tarihinde erişildi.
5. https://en.wikipedia.org/wiki/Recursion_(computer_science), en son 26.03.2015 tarihinde erişildi.
6. https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms, en son 26.03.2015 tarihinde erişildi.

Neslihan Şirin Saygılı

Posts

İTÜ Bilgisayar Mühendisliği bölümünden mezunum, şimdi doktora öğrencisiyim. Temel olarak ilgilendiğim alanlar bilgi edinilmesi (information retrieval), verinin işlenmesi (metin sınıflandırma, yazar tespiti) ve bu verinin bilgiye dönüştürülmesidir. Python, Java, PHP, Ubuntu, HTTP yığını, Linux-Apache-MySQL üçlüsü gündelik olarak kullandığım araçlardır. Prisync'in kurucu yazılımcılarından biriyim.

No Comments

Be the first to start the conversation.

Yorum yapmak için