İçeriği Paylaş:

Kabarcık Sıralama (Bubble Sort) Algoritması

Kabarcık Sıralama (Bubble Sort) Algoritması

Yer değiştirme sıralama (Exchange sort) olarak da bilinen anlaşılması kolay bir algoritmadır. Dizide yer alan her eleman, sırayla kendisinden sonra gelen elemanla karşılaştırılır ve gerekiyorsa yer değiştirilir. Sıralama işlemi yer değiştirme olduğu sürece devam eder.Kabarcık sıralamada dizi elemanlarının sayısının fazla olması durumunda işlem zamanı artar.Kabarcık algoritma kullanarak dizi elemanlarının artan şekilde sıralanması için gerekli işlem basamakları sıralanırsa;

  1. Sıraya konulmamış elemanların her birinin değeri, bir sonraki değerle yani komşu ile karşılaştırılır.
  2. Eğer karşılaştırılan değer komşu elemandan daha büyükse, komşusu ile yer değiştirilir. Böylece sıralı olmayan elemanlar her tarandığında, sadece yan yana bulunan iki eleman arasında sıralama yapılmış olur. Dizinin başından sonuna kadar tüm elemanlar bir kez işleme tabi tutulduğunda dizinin son elemanı en büyük eleman haline gelecektir. (Yani ilk geçişe, dizi içerisindeki en büyük eleman e sona )
  3. Tüm elemanlar sıralanana kadar, sıralanmamış elemanların taranma işlemi tekrarlanır.

Ekran AlıntısıÖrnek  şema  incelenirse  iç  döngünün  bir  kez  işletilmesi sonucu,dizideki en büyük değer en alta gider. Daha sonra tekrar aynı tarama yapılır. Ama bu sefer en sona kadar değil 5. Elemana kadar gidilir. Bu şekilde tüm liste taranır. Eğer son taramada bir değişiklik olmamışsa tarama işlemi bitirilir. Sonuçta küçükten büyüğe sıralanmış bir dizi elde edilir. İlk taramada görüleceği gibi elemanlardan bir örnekte 47 en sona gitmiş ve sıralı hale gelmiştir. Her adımda dizi elemanlarının nasıl tarandığı aşağıdaki şemada gösterilmiştir.Ekran AlıntısıEkran AlıntısıAkış ŞemasıEkran AlıntısıHızlı Sıralama (Quick Sort) Algoritması Hızlı sıralama algoritması böl ve yönet politikasına dayanır; sıralanması istenen dizi belirli bir karşılaştırma (pivot) değerine göre iki alt diziye ayrılır. İkiye ayırma işlemi, bu karşılaştırma değerinden küçük olan elemanlar bir tarafta, büyük olan elemanlar diğer tarafta yerleştirilerek yapılır. Bu işlem geriye kalan her bölme üzerinde tekrarlanır. Karşılaştırma değeri ya rastgele seçilir ya da dizideki az sayıda elemanın değerinin ortalaması alınır. Hızlı sıralama algoritması  en etkin (en hızlı çalışan) algoritma olmasına rağmen az sayıda elemana sahip dizilerde veya zaten neredeyse sıralı olan dizilerde tekrarlanan çağrılardan dolayı tercih edilmeyebilir. Hızlı arama algoritmasında recursive (özyinelemeli) yapı kullanılır.Hızlı sıralama algoritmasını kullanarak dizi elemanlarını artan şekilde sıralamak için gerekli işlem basamakları:

  1. İlk olarak sıralanacak diziyi ikiye bölmek için bir pivot (karşılaştırma değeri) seçilir. Pivot genellikle verilen dizinin ilk elemanı ya da son elemanı olabilir. Dizide pivottan büyük elemanlar pivotun sağına (üst), pivottan küçük elemanlar ise pivotun soluna (alt) konur. Pivot ise oluşan bu iki kümenin ortasına (orta) yerleşir. Böylece verilen dizi birbirinden bağımsız olarak iki alt diziye ayrılmış
  2. Hızlı sıralama algoritması bağımsız bu iki alt dizi (üst ve alt) içerisinde de recursive olarak çağrılır ve bu diziler kendi içerisinde 1.adım tekrarlanarak ikiye ayrılırlar. Bu işlemler diziler parçalanmayacak duruma gelene kadar tekrarlanır.

Ekran Alıntısı

  1. Sıralanacak dizinin son sayısı (13) pivot elemanı (karşılaştırma) olarak seçilir. Bu eleman daha sonraki arama ve yer değiştirme işlemlerine tabi
  2. Sol başta pivot elemanı 13’ten büyük olan ilk sayı bulunur ve sağ baştan 13’den küçük ilk sayı bulunur. Daha sonra bu iki sayı yer değiştirilir.
  3. Soldan pivot elemanından (13) büyük ve sağdan pivot elemanından küçük sayılar ortada buluşana kadar 2.adım tekrarlanır.
  4. Adımda soldan 13’ ten büyük ve sağdan 13’ten küçük sayılarortada buluştuğu için (5 ve 83) 13 ile 83 yer değiştirir. Pivotun solundaki alt dizi ve sağındaki üst dizi kendi içinde aynı teknikle sıralanır.

Akış Şeması

Ekran Alıntısı 

İçeriği Paylaş:
İlginizi Çekebilir
Yorum Yapılmamış

Henüz Hiç Yorum Yapılmadı..

Yorum Yaz

Kabarcık Sıralama (Bubble Sort) Algoritması

Programlama 2

9/08/2016 | Yorum Yok | 148 | kucukakarsu