Bubble Sort

Nedir

Listedeki elemanlari buyukten kucuge veya kucukten buyuge olacak sekilde siralayabilecegimiz bir algoritmadir.

Adinin bubble olmasi sebebi ise, bubble ingilizcede kabarcik,balon gibi anlamlara gelmektedir. Gazoz sisesindeki hava kabarciklarinin yukariya cikip bir araya toplanmasi gibi. Bu algoritmada da kucuk veya buyuk olan elemanlarin bir araya gelmesine benzetilebilir. Why is it called a bubble sort?

Nasil Calisir

Listedeki her bir eleman bir sonraki eleman ile karsilastirilarak belirlenen kosul icerisinde (buyuk veya kucuk) siranin sonuna dogru yer degisimi yapilarak suruklenir.

Baska bir deyis ile. Her bir eleman bir sonraki eleman ile kontrol edilir ve her adimda belirlenen kosula gore iki eleman arasinda yer degisimi yapilabilir.

Daha sonra listenin bir sonraki elemani icin ayni islem uygulanir. Bu sekilde butun sayilar belirlenen kosul icerisinde dizilmis olur.

Bu alogritmada iki adet ic ice dongu olmasi gerektigi icin Big-O notation degeri O(n²) dir. En iyi ihtimalde ise tum degerler birbirine esit olabilir bu durumda N x 1 defa dongu olacagi icin. BigO degeri O(n) dir.

Avantajlar

Bubble sort bize ilk dongude eger varsa aranan (en buyuk veya en kucuk) sayiyi bulmayi garanti eder.

Pagination (Sayfalandirma) ile kullanildigi takdirde. (Ornegin sayfa basina 10 adet gostermek gibi). Ilk sayfa gosterimde iken ikinci sayfa icin hesaplama devam eder bu sayede. Hizli response(yanit) durumlarinda gayet kullanisli olacaktir.

Ozet

Her bir eleman bir sonraki elemanla aralarinda; kosula gore degisim yapilarak, siranin sonuna dogru itilir.

Ornek

  const list = [100, 500, 2300, 2403, 1020, 30, 40, 200, 20, 10, 0];

  const n = list.length;

  // her bir elemani okuyacak olan dongumuz.
  for (let i = 0; i < n; i++) {
    let swap = false;

    // n-i-1 kismi dizilmis olanlari tekrar kontrol etmemek icin.
    for (let j = 0; j < n - i - 1; j++) {

      if (list[j] > list[j + 1]) {
        const temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
        swap = true;
      }

    }

    /* 
      Eger ilk dongude hic bir degisim yasanmadi ise. 
      Tum degerlerin birbirine esit oldugu anlami cikar.
      Dolayisiyla dongu durdurulur.
    */
    if (swap == false) break;
  }

https://www.geeksforgeeks.org/bubble-sort/ https://www.youtube.com/watch?v=xli_FI7CuzA https://www.youtube.com/watch?v=Jdtq5uKz-w4