### 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 as an already sorted portion of the entire input array.
- compare arr to each elem of the already sorted portion and insert where it fits.
- now arr and arr are sorted, then insert arr where it fits into the already sorted array.
- repeat the same operation for the rest of the array, for arr, arr, so on.

e.g.
lets say you already sorted arr to arr, then you start comparing arr to arr,arr,arr,, so on.
if (arr < arr[i]) then insert arr 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);

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: