Insertion sort

 
############################# 
####   insertion sort    #### 
############################# 
 
lets say we have an array of N elements to sort. and we want to sort in the ascending order. 
 
## 
## algo logic 
## 
 
- take arr[0] as an already sorted portion of the entire input array. 
- compare arr[1] to each elem of the already sorted portion and insert where it fits. 
- now arr[0] and arr[1] are sorted, then insert arr[2] where it fits into the already sorted array. 
- repeat the same operation for the rest of the array, for arr[3], arr[4], so on. 
 
e.g. 
lets say you already sorted arr[0] to arr[5], then you start comparing arr[6] to arr[5],arr[4],arr[3],, so on. 
if (arr[6] < arr[i]) then insert arr[6] to arr[i] and shift the rest by one. 
 
====> it is a simple linear search, but if you use binary search, it can be more efficient. more discussion to follow in a later section below. 
 
 
- a stable sort (depends on the implementation of the search func) 
 
 
(ref) 
http://en.wikipedia.org/wiki/Insertion_sort 
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/004.html 
 
 
 
#################################### 
####   computation complexity   #### 
#################################### 
 
 
worst case:    O(N^2) 
best case:     O(N) 
average case:  O(N^2) 
 
 
### 
### worst 
### 
 
assuming we want to sort in the ascending order, and if the smaller values are at the end of the input array/list, then the linear search/compare goes thru the whole already-sorted-subarray. as you can imagine, the worst input is the array sorted in the reverse order. 
 
input element size: N 
loop: N-1 times 
compare operation in each of N-1 loop: 1,2,3,4,,,N-1 
swap operation if using array:        1,2,3,4,,,N-1 
swap operation if using linked list:  1,1,1,,,1 
 
1 + 2 + 3 + ... + (N-2) + (N-1) = N(N-1)/2 
 
===>  now times 2 for array case, because we need to add up both comparison and swap operations 
===>  either case,  it's  O(N^2) 
 
 
 
### 
### best 
### 
 
if the input is completely sorted, and assuming we use linear search, then one comparison(to the right most elem of the already sorted sub-array) in each of N-1 looping. no swap. thus O(N) 
 
### 
### average 
### 
 
assuming the uniform random distribution of input data, still we need N-1 times looping. 
but the comparison operation in each of the loop can be cut by half. 
 
1/2 + 2/2 + 3/2 + 4/2 + ... + (N-1)/2 = N(N-1)/4    // still quadratic 
 
 
 
################################################ 
####   insertion sort using binary search   #### 
################################################ 
 
this will let you improve the search(compare) operation from O(N) to (log N) but swap still remains O(N) for the worst/average case. 
and a plain linked list does not let you do binary search, so even if you employ binary search, the worst/average complexity of insertion sort is O(N^2) 
 
in fact, the best case will be exacerbated from O(N) to O(N log N) 
 
(ref) 
http://www.brpreiss.com/books/opus4/html/page491.html 
http://stackoverflow.com/questions/7645785/is-it-possible-to-apply-binary-search-to-link-list-to-find-an-element 
http://learn.hackerearth.com/tutorial/sorting-algorithm/67/binary-insertion-sort/ 
http://stackoverflow.com/questions/18022192/insertion-sort-with-binary-search 
 
 
if you really want to improve, then you end up implementing binary tree or heap for the already-sorted-subsection, then it's no longer really a simple insertion sort. but rather, it's heap sort, or binary tree sort. 
 
 
 
############################### 
####   space complexity    #### 
############################### 
 
total:      O(N) 
auxiliary:  O(1)   // for swap, and shifting, we need at least a tmp var. technically we can do swap without any tmp var, but anyway. 
 
 
 
########################################### 
####    implementation example (C++)   #### 
########################################### 
 
lets use a straight linear search insertion sort using an array. 
 
-------------------------------------------  // main.cpp 
 
#include <iostream> 
using namespace std; 
 
void insertionSort(int*arr, int arrSize) 

  for( int i = 1; i < arrSize ;i++) 
    { 
      int pivot = arr[i]; 
      for(int j = i -1  ; j > -1; j--) 
        { 
          if(arr[j] > pivot)         // swap as long as pivot is smaller 
            { 
              arr[j] = arr[j] + arr[j+1]; 
              arr[j+1] = arr[j] - arr[j+1]; 
              arr[j] = arr[j] - arr[j+1]; 
            } 
          else                       // stop and break out cos pivot now sits where it fits 
            break; 
        } 
    } 

 
void printArr(int*arr, int arrSize) 

  for(int i = 0; i < arrSize ;i++) 
    cout << arr[i] << " "; 
  cout << endl; 

 
int main() 

  int arr[] = {92,35,84,11,4,17,66,20}; 
  int arrSize = sizeof(arr)/sizeof(arr[0]); 
 
  printArr(arr,arrSize);       // 92 35 84 11 4 17 66 20 
  insertionSort(arr,arrSize); 
  printArr(arr,arrSize);       // 4 11 17 20 35 66 84 92 
 
 
  return 0; 

 
-------------------------------------------- 
 

  1. 2014-06-07 15:14:04 |
  2. Category : algo
  3. Page View:

Google Ads