Insertion Sort

• Algorithms Lesson 2: Insertion Sort

worst case: n^2

http://www.youtube.com/watch?v=c4BRHC7kTaQ&feature=fvwrel

• Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort
More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort

for i ? 1 to i ? length(A)-1
   {
     // A[ i ] is added in the sorted sequence A[0, .. i-1]
     // save A[i] to make a hole at index iHole
     item ? A[i]
     iHole ? i
     // keep moving the hole to next smaller index until A[iHole - 1] is <= item
     while iHole > 0 and A[iHole - 1] > item
       {
         // move hole to next smaller index
         A[iHole] ? A[iHole - 1]
         iHole ? iHole - 1
       }
     // put item in the hole
     A[iHole] ? item
   }
 
http://en.wikipedia.org/wiki/Insertion_sort

• The ideas of insertion

The main operation of the algorithm is insertion. The task is to insert a value into the sorted part of the array.

Java implementation

void insertionSort(int[] arr) {
      int i, j, newValue;
      for (i = 1; i < arr.length; i++) {
            newValue = arr[i];
            j = i;
            while (j > 0 && arr[j - 1] > newValue) {
                  arr[j] = arr[j - 1];
                  j--;
            }
            arr[j] = newValue;
      }
}


http://www.algolist.net/Algorithms/Sorting/Insertion_sort