Simple Sort

 
######################### 
####   simple sort   #### 
######################### 
 
- take array[0], and compare with the rest of the array one by one. swap if array[0] > array[j] 
- at the end of this iteration, you got the min item at array[0] 
- now start from array[1] and compare with the rest, repeat 
(very much like the bubble sort) 
 
(ref) 
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/001.html 
 
- an unstable sort 
 
 
############################ 
####    code example    #### 
############################ 
 
--------------------------------------------------- 
#include <iostream> 
#include <string> 
#include <fstream> 
#include <vector> 
using namespace std; 
 
void simple_sort(vector<int> *vecp) 

  for (int i = 0; i < vecp->size(); i++){ 
    for(int j = i+1; j < vecp->size(); j++){ 
      if( (*vecp)[i] > (*vecp)[j]){ 
        (*vecp)[i] = (*vecp)[i] + (*vecp)[j]; 
        (*vecp)[j] = (*vecp)[i] - (*vecp)[j]; 
        (*vecp)[i] = (*vecp)[i] - (*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); 
  simple_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 te 
rminate the operation, thus O(n). 
 
again, pretty much like the bubble sort. 
 

  1. 2014-06-04 01:04:46 |
  2. Category : algo
  3. Page View:

Google Ads