Sıralama ve Arama Algoritmaları

Konu Anlatımı

Sıralama ve Arama Algoritmaları

Bir dizideki on iki sayının karışık hâlde durması ile aynı sayıların artan düzende sıralı olması, o sayılar arasında arama yapılırken harcanan işi tamamen değiştirir. Sıralama algoritmaları veriyi istenen düzene getirir; arama algoritmaları ise sıralı ya da sırasız veride istenen değeri bulmaya çalışır. Bu konuda her iki işlem de küçük ölçekli örneklerle ele alınacak ve karşılaştırma sayısı üzerinden hangi yöntemin ne zaman daha verimli olduğu gösterilecektir.

Bu derste ne öğreneceğiz?

Bu konuda üç temel sıralama algoritmasının nasıl çalıştığını adım adım öğreneceğiz. Kabarcık sıralama, seçme sıralama ve eklemeli sıralama için küçük diziler üzerinde elle takip yapıp hangi elemanın ne zaman yer değiştirdiğini göstereceğiz. Ardından sıralı arama ile ikili aramanın farkını inceleyecek, arama için ön koşul olup olmadığını sorgulayacağız. Son olarak karşılaştırma sayısının veri boyutuna nasıl bağlandığını sayısal örneklerle tartışacağız.

Ön bilgi

Ön bilgi olarak dizi kavramı gerekir. Dizi, aynı veri tipinde olan değerlerin sıralı biçimde bellekte tutulduğu yapıdır ve her dizi elemanının bir sıra numarası vardır. Dizi elemanına erişmek, sıra numarasını bilmeyi gerektirir; sıra numarası bilinmiyorsa arama yapılmak zorundadır.

İkinci ön bilgi, döngü içinde koşul kullanımıdır. Sıralama algoritmaları iç içe iki döngü kurar: dış döngü kaçıncı turda olunduğunu, iç döngü hangi eleman çiftinin karşılaştırılacağını belirler. Dizi elemanlarını karşılaştırıp yer değiştirmek için üçüncü bir işlem gerekir; bu işlem geçici bir değişken kullanılarak yapılır.

Sıralama nedir, neden gerekir?

Sıralama, dizi elemanlarını bir ölçüte göre yeniden dizmektir. Ölçüt çoğunlukla sayısal büyüklük ya da alfabetik sıradır. Sıralamanın temel yararı arama hızını artırmasıdır: sıralı bir dizide bir değerin bulunup bulunmadığı ilk bakışta anlaşılabilir, sırasız dizide ise baştan sona taramak gerekir.

İkinci yararı veri okunabilirliğidir. Sıralı bir liste, insan gözünde çok daha hızlı taranır. Üçüncü yararı ise bazı işlemlerde verinin önceden hazırlanmış olmasıdır: en küçük, en büyük, ortanca değerler sıralı dizide bir bakışta bulunur. Bu yüzden sıralama yalnızca bir görsel düzen değil, sonraki adımları hızlandıran bir hazırlıktır.

Kabarcık sıralaması

Kabarcık sıralamada yan yana iki eleman karşılaştırılır; sıralama düzenine aykırı olan küçük eleman sola, büyük eleman sağa geçirilir. Bir tur içinde dizi baştan sona taranır ve bu sırada büyük elemanlar kademeli olarak sağa doğru yerleşir. Her turda en büyük eleman sonuna oturduğu için dış döngüde bir eleman eksik kalmış gibi davranılır.

En kötü durumda n elemanlı dizide dış döngü n eksi bir kez, iç döngü her turda bir azalarak çalışır. Karşılaştırma sayısı toplamı 1'den n eksi 1'e kadar olan sayıların toplamıdır. Dört elemanlı bir dizide bu toplam 4 + 3 + 2 + 1 = 10 karşılaştırmadır. Dizi baştan ters sırada ise bu en kötü durum gerçekleşir; zaten sıralı bir dizide ise ilk turda hiç yer değiştirme olmaz ve algoritma erkenden durdurulabilir.

Seçme sıralaması

Seçme sıralamasında her turda dizinin kalan bölümündeki en küçük eleman bulunur ve o eleman, bölümün başındaki konuma taşınır. Böylece elemanlar yavaş yavaş yerlerine oturur. Karşılaştırma sayısı kabarcık sıralamasıyla aynı toplama dayanır, ancak yer değiştirme sayısı çok daha azdır; çünkü bir turda en fazla bir yer değiştirme yapılır.

Sekiz elemanlı bir dizide en kötü durumdaki toplam karşılaştırma sayısı 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36'dır. Bu toplam, dizi eleman sayısı arttıkça hızla büyür; bu yüzden seçme sıralaması az elemanlı dizilerde anlatımı kolay olduğu için öğretim amaçlı, çok elemanlı gerçek veride ise verimsiz olduğu için tercih edilmez.

Eklemeli sıralaması

Eklemeli sıralamada dizinin başındaki küçük bir bölümün sıralı olduğu varsayılır. Her adımda dizideki bir sonraki eleman alınır ve soldaki sıralı bölümde doğru yeri bulunana kadar geriye doğru kaydırılır. Bu kaydırma işlemi, yelkenli bir gemiyi limana yanaştırırken halatın geriye doğru çekilmesine benzer.

Beş elemana eklemeli sıralama uygulanırsa en kötü durumdaki karşılaştırma toplamı 1 + 2 + 3 + 4 = 10'dur. Veri çoktan sıralıysa her eleman ilk denemede yerine oturur ve toplam karşılaştırma sayısı eleman sayısına yakın kalır. Bu davranış, veri yavaş yavaş gelen bir listede eklemeli sıralamayı pratikte çok verimli kılar.

Sıralı arama ve sırasız arama

Sıralı arama, diziyi baştan sona tarayarak hedefi arar ve dizinin sıralı olup olmadığına bakmaz. Doğru çalışması için ön koşulu yoktur; fakat en kötü durumda hedef sonda ise bütün elemanlar karşılaştırılır. Dizi uzunluğu n ise en kötü durumdaki karşılaştırma sayısı doğrudan n olur.

Ortalama ise daha iyimserdir. Aranan değerin listenin herhangi bir yerinde eşit olasılıkla bulunduğu kabul edilirse, o n elemanlı dizide ortalama 1000 / 2 = 500 karşılaştırma yapılır. Bu ortalama, arama sonucunun her seferinde aynı yerde olmadığını gösterir; belli bir değeri sık arayan bir program için bu ortalama yanıltıcı olabilir.

İkili arama

İkili arama yalnızca sıralı dizilerde çalışır. Dizinin ortasındaki eleman hedefle karşılaştırılır; hedef daha küçükse sol yarı, daha büyükse sağ yarı alınır ve arama yalnızca bu yarı üzerinde sürdürülür. Her adımda arama alanı yarıya iner, bu yüzden çok sayıda eleman bulunsa bile sonuç hızla yaklaşır.

Üç elemanlı bir dizide arama en fazla iki adımda sonuçlanır: ilk adımda ortadaki eleman denenir, gerekirse kalan bölge en çok iki elemandır ve ikinci adımda onlardan biri denenir. Genel olarak n elemanlı dizide en fazla log2 n adım gerekir. Bin elemanlı bir dizide bu sayı on adımdır; oysa sıralı arama aynı işi bin adımda yapabilir.

Karşılaştırma sayısı ve büyüme hızı

Bir algoritmanın kaç adım çalıştığı, veri sayısı arttıkça nasıl büyüdüğüyle tanımlanır. Doğrusal büyüyen algoritmalarda adım sayısı veri sayısıyla, logaritmik büyüyenlerde ise çok daha yavaş artar. Bu ayrım, küçük listede fark edilmezken büyük listede belirleyici hâle gelir.

Somut olarak düşünülsün: yüz elemanlı bir dizide sıralı arama en fazla yüz karşılaştırma yaparken ikili arama en fazla yedi adımda sonuçlanır. On bin elemanlı bir dizide sıralı aramanın sınırı on bin olurken ikili aramanın sınırı on dört adımda kalır. Veri sayısı iki katına çıktığında doğrusal yöntemin yükü iki katına çıkarken logaritmik yöntemin yükü yalnızca bir adım büyür.

Kararlı sıralama ve ikinci ölçüt

İki elemanın değerleri eşitse, aralarındaki önceki sıralamanın korunup korunmadığına kararlı sıralama denir. Kararlı sıralama, ikinci bir ölçüt gerektiğinde önem kazanır: örneğin önce puana, puana eşit olanlarda ise numaraya göre sıralama yapılacaksa, kararlı bir yöntem numara sırasını korur.

Kararlı olmayan bir yöntemde aynı değerli iki kayıt yer değiştirebilir ve numara sırası bozulabilir. Bu nedenle kayıt sıralaması yapılan programlarda yöntemin kararlılığına bakılmalı, gerekiyorsa kararlı sıralama tercih edilmelidir.

Basit örnek

Dört elemanlı bir dizi düşünülsün: 5, 2, 8, 3. Kabarcık sıralamanın ilk turunda 5 ile 2 karşılaştırılır ve sıralama düzenine aykırı oldukları için yer değiştirirler; dizi 2, 5, 8, 3 olur. Aynı turda 5 ile 8 karşılaştırılır, sıralama düzenine uygun olduğu için yer değiştirme olmaz. 8 ile 3 karşılaştırılır ve yer değiştirirler; dizi 2, 5, 3, 8 olur.

İlk turda en büyük eleman olan 8 sona oturmuştur. İkinci turda 2, 5 ve 3 elemanlarına sıralama uygulanır ve dizi 2, 3, 5, 8 olur. Dizi ilk iki turdan sonra sıralı hâle gelir ve kalan turlarda yer değiştirme olmaz.

İleri örnek

Bir öğrenci listesi puana göre sıralanacaktır. Listede aynı puana sahip öğrenciler bulunduğundan ikinci bir ölçüt gerekir: öğrenci numarası. Bu durumda iki aşamalı bir çözüm kurulur. Önce liste puana göre sıralanır, sonra puana göre gruplar belirlenir ve her grup kendi içinde öğrenci numarasına göre yeniden sıralanır.

Bu çözümde ilk sıralamada kararlılık önemlidir; ikinci sıralama yalnızca aynı puanlıları etkiler. Alternatif olarak seçme sıralaması iki ölçütü tek adımda karşılaştırma fonksiyonuna verebilir. Hangi yolun seçileceği, listenin uzunluğuna ve kararlılık ihtiyacına göre belirlenir.

Adım adım çözülmüş örnek

Görev: 4, 11, 7, 2 dizisini seçme sıralamasıyla artan düzende sıralamak. Çözüm: Adım 1: Kalan bölüm 4, 11, 7, 2 olarak alınır ve en küçük eleman olan 2 bulunur. Adım 2: 2, ilk konuma taşınır; dizi 2, 4, 11, 7 olur. Adım 3: Kalan bölüm 4, 11, 7 taranır, en küçük eleman 4'tür ve yerinde kalır. Adım 4: Kalan bölüm 11, 7 taranır, en küçük eleman 7'dir ve üçüncü konuma taşınır; dizi 2, 4, 7, 11 olur.

Dört tur sonunda dizinin ilk üç konumu kesinleşmiştir ve son konumda kalan eleman otomatik olarak doğru yerde durur. Dört eleman için toplam karşılaştırma sayısı 4 + 3 + 2 + 1 = 10'dur; bu sayı elemanların başlangıç sırasından bağımsızdır.

Kavram karşılaştırma tablosu

Sık Yapılan Hatalar

• Hata: Karşılaştırma yapılmadan yer değiştirmek. Doğrusu: Önce karşılaştırılır, yalnızca sıralama düzenine aykırıysa yer değiştirilir.
• Hata: Sırasız dizide ikili arama yapmak. Doğrusu: İkili aramanın ön koşulu dizinin sıralı olmasıdır.
• Hata: Dış döngüyü eleman sayısı kadar tekrarlamak. Doğrusu: Son eleman kendiliğinden yerine oturduğu için dış döngü bir kez daha az çalışır.
• Hata: İç döngü sınırını sabit tutmak. Doğrusu: Her turda sıralanan bölüm büyüdüğü için iç döngü sınırı bir azaltılır.
• Hata: Arama sonucunu bulunamadı hâlinde sıfır sanmak. Doğrusu: Bulunamadı durumu ayrı bir değerle bildirilir.
• Hata: Karşılaştırma sayısını sabit bir sayı sanmak. Doğrusu: Sayı veri uzunluğuyla birlikte değişir ve genellikle doğrusal büyür.
• Hata: Yer değiştirme yaparken üçüncü bir geçici değer kullanmamak. Doğrusu: Bir elemanın üzerine yazılmaması için geçici bir değişken gerekir.
• Hata: Aynı puanlı kayıtların sırasını önemsememek. Doğrusu: İkinci ölçüt varsa kararlı sıralama tercih edilmelidir.

Özet

Sıralama algoritmaları dizi elemanlarını istenen düzene getirir. Kabarcık sıralama yan yana elemanları karşılaştırıp yer değiştirir; seçme sıralama her turda en küçük elemanı bulup yerine taşır; eklemeli sıralama ise her yeni elemanı soldaki sıralı bölüme yerleştirir. Üçünün de karşılaştırma sayısı veri sayısıyla doğrusal büyür. Sıralı arama diziyi baştan sona tarar ve sıralı olma koşulu taşımaz. İkili arama ise ortadan başlayıp arama alanını her adımda yarıya indirir; bu yüzden sıralı dizi koşuluna bağlıdır. Eşit değerli elemanların sırasını koruyan yöntemler kararlı sıralama olarak adlandırılır.

Kendini dene

Kendin dene bölümünde kendi seçtiğin beş elemanlık bir diziyle çalış. Önce kabarcık sıralamanın her turunu kâğıda yazarak dizinin hâlini çiz, sonra aynı diziyi seçme sıralamasıyla sırala ve iki yöntemin yer değiştirme sayılarını karşılaştır. Son olarak diziyi sıraladıktan sonra ikili aramayla bulunması gereken bir değeri ara ve adım sayısını yaz. Puanlama notu: her turun hangi eleman çiftinin karşılaştırıldığını yazmayan çalışma eksik sayılır.