Bubble Sort

 
############################ 
####    bubble sort     #### 
############################ 
 
basically, when you have an array of size N, bubble up the heaviest item to the end, then repeat the same operation for the array 0 to N-1. 
 
- start from comparing array[0] versus array[1] 
- if array[0] > array[1] then swap. (assuming we are sorting in the ascending order.) 
- then next, compare array[1] versus array[2] 
- increment the index until reaching the end of array. 
(at this point, the biggest value bubbled to the end.) 
- start over, but stop at the index before the end cos the last index is the heaviest which itself is already in the sorted position. 
 
(ref)  // good visualized delineation 
http://en.wikipedia.org/wiki/Bubble_sort 
 
- a stable sort 
 
 
 
################################# 
####    code example (c++)   #### 
################################# 
 
--------------------------------------------------- 
 
#include <iostream> 
#include <string> 
#include <fstream> 
#include <vector> 
using namespace std; 
 
 
void bubble_sort(vector<int> *vecp) 

  for (int i = 0; i < vecp->size(); i++){ 
    for(int j = 1; j < vecp->size() - i; j++){ 
      if( (*vecp)[j-1] > (*vecp)[j]){ 
        (*vecp)[j-1] = (*vecp)[j-1] + (*vecp)[j]; 
        (*vecp)[j] = (*vecp)[j-1] - (*vecp)[j]; 
        (*vecp)[j-1] = (*vecp)[j-1] - (*vecp)[j]; 
      } 
    } 
  } 
  return; 

 
void display(vector<int> vec) 

  for (int i = 0; i < vec.size(); i++) 
    { 
      cout << vec[i] << ' '; 
    } 
  cout << endl; 
  return; 

 
int main() 

  int arr[5] = {12, 343, 122, 848, 49}; 
  vector<int> vec (arr, arr+5); 
  display(vec); 
  bubble_sort(&vec); 
  display(vec); 
  return 0; 

 
------------------------------------------------- 
 
 
#################################### 
####   computation complexity   #### 
#################################### 
 
best case performance:     O(n) 
worst case performance:    O(n^2) 
average case performance:  O(n^2) 
 
worst case space : O(1) 
 
------- 
best case is when you have the already completely sorted list, then the first iteration without any swap can terminate the operation, thus O(n). 
 
average case is; when you have N items, there can be N(N-1)/2 pairs. assuming half of them require swap, it will be N(N-1)/4, which will not beat polynomial of degree 2. 
 
 
(ref) 
http://cs.stackexchange.com/questions/20/evaluating-the-average-time-complexity-of-a-given-bubblesort-algorithm 
 

  1. 2014-05-27 22:58:55 |
  2. Category : algo
  3. Page View:

Google Ads