亘古微博
咨询邮箱:nicholas@anycle.com
您的位置:网站首页 > 新闻动态 > 算法专题 >
[C] Bubble sort
来源:未知 作者:admin 发表于:2015-03-11 16:07  点击
Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.
 
The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).
 
Bubble sort should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.


Example:

#include <iostream>
#include "bubble.h"
using namespace std;
 
#define LENGTH 10
#define ORG_DATA 1,2,3,4,5,6,7,8,9,10
 
void bubble(){
      int data[LENGTH] = {ORG_DATA};
      int len = LENGTH;
      int tmp;
      bool over=false;
      int o_count = 0;
 
      cout<<"bubble"<<std::endl;
      for(int i=0; i<len; i++){
           cout<<data[i]<<",";
      }
      cout<< std::endl << "****************"<<std::endl;
     
      len--;
      for(i=0; i<len; i++){
           over=true;
           for(int j=0; j<len-i; j++){
                 o_count ++;
                 if(data[j]>data[j+1]){
                      over=false;
                      tmp = data[j+1];
                      data[j+1] = data[j];
                      data[j] = tmp;
                 }         
           }
           if(over){
                 break;
           }
      }
      len++;
 
      for(i=0; i<len; i++){
           cout<<data[i]<<",";
      }
      cout << std::endl;
     
      cout << "***********************" << std::endl;
      cout << o_count << std::endl;
}
相关文章推荐
[C] Insertion sort

This is the insertion sort function by nicholas....

[C] Binary sort

Just a simple example of binary sort....

[C] Bubble sort

Bubble sort should be avoided in the case of large collections. It will not be ef...

[JS] How boys and girls stand balance

How boys and girls stand balance...