Ünite 7: Sıralama Algoritmaları

Giriş

Sıralama, genel olarak dizilerin veya herhangi bir veri yapısının elemanlarının istenilen düzene getirilmesi olarak ifade edilebilir. Sıralanmak istenilen elemanlar, sayılar veya metinsel ifadeler gibi kavramlar olabilir. Bu ünitemizde, sayısal veriler içeren dizilerin sıralanması üzerinde durulacaktır. Bu amaçla geliştirilmiş çeşitli sıralama algoritmaları bulunmaktadır. Baloncuk sıralaması (bubble sort), seçmeli sıralama (selection sort), araya sokarak sıralama (insertion sort), hızlı sıralama (quick sort), birleştirerek sıralama (merge sort), yığın sıralaması (heap sort) gibi algoritmalar temel sıralama algoritmalarıdır. Bu algoritmaların hepsinin kendine özel çalışma mantıkları bulunmaktadır. Baloncuk sıralaması, dizinin her konumundaki elemanlarının sırasıyla sonraki konumdaki elemanlarla karşılaştırılması ve gerekli durumlarda komşu elemanların yer değiştirmesine dayanır. Seçmeli sıralama, küçükten büyüğe doğru yapılacak bir sıralama işleminde her defasında dizinin en küçük elemanının tespit edilmesi ve uygun konuma yerleştirilmesine dayanır. Araya sokarak sıralama, diziden seçilen bir elemanın diğer elemanların kaydırılması vasıtasıyla uygun boşluğa yerleştirilmesi olarak açıklanabilir. Hızlı sıralama, dizinin genellikle orta noktasında bulunup pivot olarak adlandırılan bir elemanın seçilmesi ve kalan elemanların pivot elemandan küçük ya da büyük olmasına göre sıralanması üzerine kurulmuş bir algoritmadır. Birleştirerek sıralama, dizilerin daha küçük alt dizilere bölünmesi ve bu alt dizilerin sıralandıktan sonra birleştirilmesi şeklinde çalışan bir algoritmadır. Yığın sıralaması, temel olarak dizinin elemanlarının bir yığın veri yapısı üzerinde temsil edilir hale getirilmesine ve sonrasında sıralanmasına dayanır.

Baloncuk Sıralaması

Dizinin her bir konumundaki elemanı, sırasıyla bir sonraki konumdaki eleman ile karşılaştırılır. Dizinin küçükten büyüğe doğru sıralanması istenirse, bu karşılaştırma esnasında mevcut elemanın sonraki dizi elemanından büyük olup olmadığı kontrol edilir. Bu şartın sağlandığı sonucuna varılırsa iki eleman yer değiştirilir. Aksi durumda ise herhangi bir yer değiştirme işlemi yapılmaz ve karşılaştırmaya bir sonraki konumdaki dizi elemanı ile devam edilir. Bu işlem dizinin son elemanına ulaşıncaya kadar sürdürülür. Dizinin başından sonuna doğru yapılan bu karşılaştırma tamamlandığında, algoritmanın bir adımı (iterasyonu) tamamlanmış olur. Bu algoritma adımları n elemanlı bir dizi için n-1 defa tekrarlandığında tamamen sıralı bir dizi elde edilmiş olunur.

Seçmeli Sıralama

Seçmeli sıralama, küçükten büyüğe doğru sıralama yapılacağı zaman adım adım dizilerin içerisindeki en küçük elemanların bulunmasına ve bu elemanların baştan itibaren uygun konumlara yerleştirilmesine dayanan bir algoritmadır. Algoritmanın başlangıcında, dizinin ilk elemanı en küçük olarak kabul edilir ve bu eleman dizideki tüm elemanlarla tek tek karşılaştırılır. Karşılaştırmaların sonunda daha küçük bir eleman tespit edilmişse bu eleman ile ilk elemanın yerleri değiştirilir. Sonraki adımlarda ise her defasında bir sonraki elemanın dizinin kalanı için en küçük eleman olduğu varsayılır ve bu karşılaştırmalara sonraki elemanlarla devam edilir. Bu karşılaştırmalar ve yer değiştirme işlemleri dizinin bütün elemanları için tamamlandığında küçükten büyüğe doğru sıralı bir dizi elde edilir. Algoritma adımları, n elemanlı bir dizi için n-1 defa tekrarlandığında tamamen sıralı bir dizi elde edilir.

Araya Sokarak Sıralama

Araya sokarak sıralama algoritması, dizinin elemanlarının kendilerinden önce gelen elemanlarla karşılaştırılması ve gerektiğinde birbirleriyle yer değiştirmeleri prensibine dayanır. Her bir adımda (iterasyonda), dizi elemanları üzerinde soldan sağa doğru hareket edilerek, kendisinden önce gelenlerle karşılaştırılacak bir anahtar eleman seçilir. Bu anahtar eleman, kendisinden önce gelen diğer tüm elemanlarla sırayla karşılaştırılır. Küçükten büyüğe doğru sıralama yaparken, kendisinden önce gelen eleman daha büyük ise bu eleman dizide sağa doğru kaydırılır. Dolayısıyla her adımda, dizide anahtar olarak seçilen eleman geçici olarak silinecektir. Bu karşılaştırma ve kaydırma işlemi, anahtar elemandan öncekiler kendisinden daha büyük olduğu sürece devam eder. Karşılaştırmalar tamamlanmışşa anahtar olarak seçilen eleman dizide uygun bir konuma yerleştirilir.

Hızlı Sıralama

Hızlı sıralama algoritması, şimdiye kadar bahsedilen sıralama algoritmalarından farklı olarak böl ve yönet (divide-and-conquer) yöntemini kullanarak sıralama işlemini gerçekleştirir. Başka bir ifadeyle, diziyi mantıksal olarak farklı parçalara ayırır ve sıraladığı parçaları daha sonra birleştirir. Ayrıca, program kodunun özyinelemeli (recursive) fonksiyon olarak yazılması söz konusudur. Özyinelemeli fonksiyonlar, kendi içlerinde tekrar kendilerini çağıran fonksiyonlardır. Bu fonksiyonlarda bir bitiş koşulu yer almaktadır. Fonksiyon, bu bitiş koşulunu sağladığında adım adım geriye değer döndürür ve sonlanır. Hızlı sıralama, dizinin içerisinden bir pivot eleman seçilmesiyle başlar. Pivot eleman, hızlı sıralama algoritmasında bölümleme için seçilen sınır değeridir. Hızlı sıralama algoritması, pivot elemandan küçük ve büyük değerleri iki farklı gruba ayırmaya çalışır. Bunun için dizinin ortasında yer alan eleman tercih edilebilir. Sonrasında pivottan küçük olduğu halde pivotun sağında yer alan elemanlar ile büyük olduğu halde pivotun solunda yer alan elemanların yerleri değiştirilir. Dolayısıyla, bu işlemin sonunda dizi, pivot elemandan küçük olanlar ve pivot elemandan büyük olanlar şeklinde iki ayrı gruba ayrılır. Daha sonra, aynı işlemler dizinin iki grubu için bağımsız olarak tekrarlanır. Algoritmanın çalışması tamamlandığında, kendi içerisinde sıralı iki dizinin birleştirilmesiyle tek bir sıralı dizi elde edilir.

Birleştirerek Sıralama

Birleştirerek sıralama, hızlı sıralama algoritması gibi özyinelemeli bir algoritmadır. Dizi, ilk olarak orta noktadan ikiye ayrılır ve bu iki dizi kendi içinde sıralanır. Hızlı sıralamadan farklı olarak dizi içerisindeki bu iki grup oluşturulurken herhangi bir sayıdan küçük veya büyük şeklinde bir ayrıma gidilmez. Sıralama işleminin yapılması için dizi, tek elemanlı hale gelene kadar ikiye ayrılır. Daha sonra, geçici diziler kullanılarak bu elemanlar sıralı olacak şekilde bir araya getirilirler.

Yığın Sıralaması

Yığın sıralaması, verileri önceki ünitelerde bahsedilen yığın veri yapısı üzerinde temsil etmeye ve o yapıyı kullanarak sıralama yapmaya dayanır. Konum değerleri sıfırdan başlayan bir dizinin yığın şeklinde gösterildiği varsayıldığında, kök i konumunda gösteriliyorsa sol alt düğüm 2*i+1 ve sağ alt düğüm 2*i+2 konumlarında yer alır.

Sıralama Algoritmalarının Özellikleri

Sıralama algoritmaları çeşitli açılardan birbirleriyle karşılaştırılabilirler. Bunların en önemlilerinin başında zaman karmaşıklığı (time complexity) kavramı gelir. Karmaşıklığı düşük olan bir algoritmanın daha hızlı çalışabileceği söylenebilir. Bir diğer önemli husus, algoritmanın istikrarlı (stable) olup olmamasıdır. Bir algoritmanın istikrarlı olması, dizi içerisinde aynı değere sahip elemanların bulunması durumunda, sıralama sonunda bu elemanların birbirlerine göre bağıl olarak yerlerinin değişmemesi anlamına gelmektedir. Aşağıda sıralama algoritmaları zaman karmaşıklığı ve istikrarlılık açısından karşılaştırılmıştır. En kötü durumdaki zaman karmaşıklıkları dikkate alınmıştır. En kötü durum ile anlatılmak istenilen husus, algoritmanın çalışmasının en uzun süreceği durumdur. Elbette, neredeyse sıralı bir dizi verildiğinde algoritmanın sıralama işlemini daha çabuk bitirebilmesi mümkün olabilir. Aşağıda da görüldüğü üzere, birleştirerek sıralama ve yığın sıralamasının diğer sıralama algoritmalarına göre daha düşük zaman karmaşıklığına sahip olduğu anlaşılmaktadır. İstikrarlılık açısından değerlendirme yapıldığında ise yığın sıralamasının ve seçmeli sıralamanın istikrarlı olmadığı görülmektedir. Hızlı sıralamanın genellikle istikrarlı olmaması ise algoritmanın kodlanması aşamasındaki yaklaşımlardan kaynaklanmaktadır.

Algoritmaların en kötü durumda zaman karşılığının istikrarlı olup olmadığı aşağıda listelenmiştir:

• Baloncuk sıralaması; O(n ² ) istikrarlı
• Seçmeli sıralama; O(n ² ) istikrarsız
• Araya sokarak sıralama; O(n ² ) istikrarlı
• Hızlı sıralama; O(n ² ) genellikle istikrarsız
• Birleştirerek sıralama; O(n*log(n)) istikrarlı
• Yığın sıralaması; O(n*log(n)) istikrarsız