Bubble Sort

氣泡排序 (Bubble Sort)

參考資料：維基百科 bubble sort

最差時間複雜度 (Worst case performance)： O(n^2)
最佳時間複雜度 (Best case performance)： O(n)
平均時間複雜度 (Average case performance)：O(n^2)
最差空間複雜度 (Worst case space complexity)： O(1) auxiliary

<style>
.container201312071100{
    width: 365px;
    height: 155px;
    border-style:solid;    
    /*border-color:#cccccc;*/
    border-width: 1px;
    padding-left: 5px;
    padding-right: 5px;  
    padding-top: 5px;
    padding-bottom: 5px;   
}

.rectangle201312071100{
    margin: 5px 5px 5px 5px;
    width: 40px;
    height: 40px;
    border-style:solid;
    border-width: 1px;  
    /*border-color:#cccccc;*/
    float: left;
    text-align: center;
    line-height: 40px;
}
</style>

<div id="container201312071100" class="container201312071100">    
</div>
<br/>
<input type="button" value="sort" id="sort201312071100" />
<input type="button" value="random" id="random201312071100"/>
<script type="text/javascript">
(function(){
    var displays=[], 
        container=document.getElementById('container201312071100'),
        sort=document.getElementById('sort201312071100'),
        random=document.getElementById('random201312071100');
        
    var init = function(){
        for(var i=0 ; i < 21 ; i++){
            displays[i] = getDisplayObject();
            container.appendChild(displays[i]);
        } 
        addListener();        
    }; 
    
    var addListener = function(){
        sort.addEventListener('click' ,doSort , false);
        random.addEventListener('click' ,doRandom , false);
    };
    
    var removeListener = function(){
        sort.removeEventListener('click' ,doSort , false);
        random.removeEventListener('click' ,doRandom , false);
    };
    
    var doSort = function(){
         removeListener();         
         
         var n1,n2;   
         //bubble sort
         for(var count=displays.length ; count > -1 ; count--){             
             for(var j=0 ; j <= count  && j+1 < count ; j++){              
                 n1 = parseInt(displays[j].textContent,10);    
                 n2 = parseInt(displays[j+1].textContent,10); 
                 if(n1 > n2){
                     displays[j+1].textContent =  displays[j].textContent;
                     displays[j].textContent =  n2;                 
                 }                 
             }
         }
         
         addListener();     
    };    
    
    var doRandom = function(){
        removeListener();        
        var count = displays.length;
        for(var i=0 ; i < count ; i++){
            displays[i].textContent  = Math.floor((Math.random()*100)+1);
        }
         addListener();
    };
    
    var getDisplayObject = function(){
      var displayObject = document.createElement('div');
          displayObject.className = 'rectangle201312071100';
          displayObject.textContent  = Math.floor((Math.random()*100)+1);
      return displayObject;
    };    

    init();   
})(); 
</script>