Web Programlama

Web Programlama

DERS PROGRAMI
Web Programlama 301 Ders Programı
Sınava Gir

Kabarcık Sıralama (Bubble Sort) Yöntemi

Lisans: Creative Commons 26.11.2020 tarihinde güncellendi
Bakabileceğiniz Etiketler: Eğitmen: Geleceği Yazanlar Ekibi

Anlaşılması kolay bir sıralama yöntemi de bubble sort (kabarcık sıralama) adı verilen yöntemdir. n elemanlı L listesini artan sırada sıralamak istediğimizi varsayalım.

Kabarcık sıralama yönteminde yer değiştirme sıralaması yönteminden farklı olarak, her geçişte listenin komşu olan elemanları birbiri ile karşılaştırılır ve ilk geçişte liste içindeki en büyük eleman en sona gider. Bundan sonraki geçiş ilk n-1 eleman arasında gerçekleştirilir ve bu geçişin sonunda da en büyük eleman n-1'nci konuma yerleşir. Benzer şekilde bir sonraki geçiş arta kalan n-2 eleman arasında gerçekleştirilir ve bu geçişte de bu en son liste parçası içindeki en büyük eleman n-2'nci yere yerleşir.

Bu işlemler benzer şekilde sürer. Herhangi bir geçişte hiçbir yer değiştirme olmamışsa liste sıralanmış demektir.

 

Kabarcık sıralama: örnek veri üzerinde adımlar

Şimdi n=5 elemanı olan L listesi aşağıdaki gibi verilmiş olsun:

1. Geçiş

Bu aşama 1. geçişin sonudur ve yukarıda da belirtildiği gibi 1. geçişin sonunda veri içindeki en büyük eleman en sona yerleşmiştir.

2. Geçiş

2. geçiş, 1. geçişin bıraktığı noktadaki liste ile başlar.

2. geçiş sona ermiş ve bu geçişte, ilk 4 elemanın en büyüğü olan 56 sondan bir önceki yere yani doğru yerine yerleşmiştir. 3. geçiş ilk 3 eleman arasında olacaktır.

3. Geçiş

L1 ile L2 mukayese edilir; 12<34 olduğu için bu iki eleman yer değiştirmez.

L2 ile L3 mukayese edilir; 34<11 olduğu için bu iki eleman yer değiştirir:

3. geçişin sonudur ve veri içindeki 3. en büyük eleman sondan 3. yere yerleşmiştir.

4. Geçiş

L1 ile L2 mukayese edilir; 12>11 olduğu için bu iki eleman yer değiştirir:

4. geçiş sona ermiştir ve verinin sıralandığı görülmektedir.

 

Kabarcık sıralaması (bubble sort) algoritması

  1. Veri listesi üzerinde birbirini izleyen geçişleri uygula.
  2. Her geçiş esnasında birbirini izleyen iki liste elemanı arasında karşılaştırma işlemi yap ve gerekiyorsa yer değiştirme işlemini gerçekleştir.
  3. Bir geçiş esnasında hiçbir yer değiştirme olmuyorsa ya da n-1 geçiş tamamlanmışsa (veri miktarının n olduğu var sayımı ile) sıralama işlemini sona erdir.

Kabarcık sıralama algoritmasında bir geçişi daha formel olarak şu şekilde ifade edebiliriz:

i=1,2,... n-1 şeklinde değişirken

Şayet Li >Li+1 ise, Li ile Li+1 ‘e yer değiştir

Kabarcık sıralama algoritmasının performansı da O(n2) mertebesindedir. Veri miktarı arttıkça sıralama için gerekli zaman veri miktarının karesi ile orantılı olarak artar.

 

Örnek: Kabarcık sıralama JavaScript uygulaması

<html>
<head>
<title> İÇİNDEKİLER </title>
</head>
<body bgColor="lightblue" text="darkblue">
<script language="JavaScript">
var a=[34,5,11,9,76,43,77,789,51,10];
var i;
var t,f;
document.write("<h3>"+"SIRALAMADAN ONCEKI DIZI"+"</h3>");
document.write("<h3>"+a.join(" ")+"</h3>");
f=0;
while(f==0){f=1;
for(i=0;i<=a.length-1;i++)
{if(a[i]>a[i+1])
{t=a[i];
a[i]=a[i+1];
a[i+1]=t;
f=0;
}}}
document.write("<h3>"+"SIRALAMA ISLEMINDEN SONRAKİ DIZI"+"</h3>");
document.write("<h3>"+a.join(" ")+"</h3>");
</script>
</body>
</html>

Sınava Gir