### 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: