iT邦幫忙

DAY 9
5

用Javascript征服演算法系列 第 6

用Javascript征服演算法 (5-bubble sort&實作)

Bubble Sort~~~像泡泡一樣會冒出排序好的集合喔~~~(最好這麼容易XD)
用Javascript征服演算法 (5-bubble sort&實作)

來到Bubble Sort囉~~!!!!這是一個簡單又可愛又簡單又可愛的sort~~~(完全跳針)
在講解Bubble Sort可以先去看這個很可愛的video(各種可愛)

https://www.youtube.com/watch?v=lyZQPjUT5B4

看完video後,再來定義一次bubble sort的排序方式吧,其實就是很簡單的概念,透過一一選取未排序集合的元素相鄰做比較,已排序的集合就會自然地出現在最後面,你說這麼神奇? 確實相對邏輯上比較沒這麼複雜,但其實複雜度都是一樣糟糟啦XD

接下來理解後就來實作囉!! 實做排序由小到大
一開始一樣是寫一個可以一一選取未排序集合的最外面的迴圈

 for(var i = 0; i < list.length; i++) { 
   //將元素及LIST丟進去處理處理阿
}

再來就是跟鄰居兒做個比較,看誰比較小啦~,如果跟鄰居比較發現他比我小,那當然就要交換位置,此時就要用到swap囉

for(var i = 0; i < end - 1; i++) {
    if(compare(list[i + 1], list[i]) < 0) {
    swap(list, i + 1, i);  

  }

}




function swap(list, i, j) {
    var ele = list[i];
    list[i] = list[j];
    list[j] = ele;
}

以上兩步驟做完就完成實作了,不過在此我們可以在針對bubble sort的特性讓程式少做幾次比較,也就是,加上判斷是否有做swap這個動作

因為在bubble sort當中,如果一旦陣列中相鄰比較都不需要做swap,那代表陣列已經排序完成了,因此我載比較的函示裡加上return是否有swap的動作

var swapornot = 0;
for(var i = 0; i < end - 1; i++) {
    if(compare(list[i + 1], list[i]) < 0) {
    swap(list, i + 1, i);  
    swapornot = 1;
  }

}
return swapornot;

由以下兩個連結可以看見加了上述動作後,有減少比較的次數喔!!!!

http://jsfiddle.net/EDr8K/
http://jsfiddle.net/EDr8K/1/

附上最終版的code

var times = 0;

function ascending(a, b) {return a - b;}


function swap(list, i, j) {
    var ele = list[i];
    list[i] = list[j];
    list[j] = ele;
}


function bubbleTo(list, to, compare) {
    var swapornot = 0;
    for(var i = 0; i < to - 1; i++) {
        if(compare(list[i + 1], list[i]) < 0) {
        swap(list, i + 1, i);  
        swapornot = 1;
      }

    }

     times++;
    return swapornot;

}

function bubbleSort(list, compare) {

    for(var i = 0; i < list.length; i++) { 
      var swap =  bubbleTo(list, list.length - i, compare); 
        if(!swap)
           break;
    }
}

var list = [10, 9, 1, 2, 5, 3, 8, 7];

bubbleSort(list, ascending);
console.log(list);
console.log(times);

暖身完畢,接下來要進入比較難的quick sort囉開心


上一篇
用Javascript征服演算法 (2-Gray Code-Javascript實作)
下一篇
用Javascript征服演算法 (6-Quick Sort)
系列文
用Javascript征服演算法10

2 則留言

0
葉宇霖
iT邦新手 4 級 ‧ 2013-10-01 21:22:20

跳針跳針跳針
唱歌唱歌

0
azole
iT邦新手 5 級 ‧ 2013-10-01 21:34:52

補充一下:
bubble sort的複雜度:
Best case: O(n)
Worst case: O(n^2)
Avg. case: O(n^2)

我要留言

立即登入留言