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