Insertion sort

1.Insertion sort

• Start with a sorted sub-list of size 1

• Insert the next element into the sorted sub-list at the time right position. Now the sorted sub-list has 2 elements.

• By inserting into a sorted sub-list at every step the sub-list soon grows to be the entire list

• 將每一個元素與右邊的元素比較, 一旦右邊的比較小, 則開始swap (跟bubble sort很像)

2.Procedures

• Insertion sort first assumes a sorted list of size 1 and inserts additional elements in the right position

3.Example code (Java)

• Insertion method

public static void insertionSort(int[] listToSort) {
    //Go up to the second to last element
    for (int i = 0; i < listToSort.length - 1; i++) {
        //Consider everything uptil the ith element sorted
        //Bubble the element element outside the sorted sub-list to the right position
        for (int j = i + 1; j > 0; j--) {
            if (listToSort[j] < listToSort[j - 1]) {
                swap(listToSort, j, j - 1);
            } else {
                //If no swap was performed the element has been moved to the right position so break out the loop
                break;
            }
        }
        print(listToSort);
    }
}

• Swap

  public static void swap(int[] listToSort, int iIndex, int jIndex) {
      int temp = listToSort[iIndex];
      listToSort[iIndex] = listToSort[jIndex];
      listToSort[jIndex] = temp;
  }

4.Complexity

• Complexity of Bubble sort is O(N^2)

• Checking "N" elements for each of "N" selected elements

• It's adaptive sort

• It takes O(1) extra space, it sorts in space (No extra space)

  • 因為用原本的list儲存 (in-place 演算法)

• It is a stable sort:

  • As entities bubble to the correct position in the sub-list that is sorted. The list the original order of entities are maintained for equal elements.

• It makes O(N^2) comparisons and O(N^2) swaps (與Bubble sort相同)

  • 比較複雜度是O(N^2)

  • 交換次數是O(N^2)

5.Insertion sort v.s bubble sort

1. Bubble sort requires an additional pass over all elements to ensure that the list is fully sorted.

2. Bubble sort has to do "N" comparisons at every step. Insertion sort can stop comparison elements when the right position in the sorted list is found.

3. Bubble sort performs poorly with modern hardware because of the number of writes and swaps that it performs. Results in cache misses so has greater overhead than insertion sort.