Insertion Sort

This algorithm sorts by inserting in the list.

Pseudocode

It works like a poker player would handle cards as he receives them from the dispatcher.

  1. He would get an initial card.
  2. He would get a second card and shuffle so he has them in order.
  3. The third card he gets he puts it at the end of the stack.
  4. Then goes inserting it to the left until it reaches the slot where there is no card with less value.
  5. Repeats the same algorithm with the next cards.

Asymptotic Analysis

  • Best case scenario it runs Θ(n).
  • Worst case scenario Θ($$n^2$$)

Therefor O(n^2)

This is more efficient than Selection Sort in the case that the list would be almost sorted.

Implementation

  1. var insert = function(array, rightIndex, value) {
  2.     for(var j = rightIndex;
  3.         j >= 0 && array[j] > value;
  4.         j--) {
  5.         array[j + 1] = array[j];
  6.     }   
  7.     array[j + 1] = value; 
  8. };
  10. var insertionSort = function(array) {
  11.     for(var i = 0; i < array.length - 1; i++) {
  12.         insert(array, i, array[i + 1]);
  13.     }
  14. };
  16. var array = [22, 11, 99, 88, 9, 7, 42];
  17. insertionSort(array);
  18. println("Array after sorting:  " + array);
  19. Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);
  22. var array2 = [100, 3300, -3, 0, 40, -34, 0];
  23. insertionSort(array2);
  24. println("Array after sorting:  " + array2);
  25. Program.assertEqual(array2, [-34,-3,0,0,40,100,3300]);