- Forward


Insertion Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • A Popular Motivation:
    • Between 25% and 50% of computing time in commercial applications is devoted to sorting
    • Hence, it is important to consider the efficiency of sorting algorithms
  • My Motivation:
    • The issues that arise are illustrative of the issues that arise when developing other algorithms
    • They provide good examples of how to find the efficiency of an algorithm
Insertion Sort
Back SMYC Forward
  • An Analogy:
    • The way people sort cards when playing poker or rummy
  • The Algorithm:
    • Sort the first two elements
    • Then, take the third element and put it in the appropriate position relative to the first two
    • Proceed iteratively until all of the elements are sorted
A Pseudcode Implementation
Back SMYC Forward
insertionsort(a[]) { for all i { move all elements larger than a[i] one position; put a[i] in the resulting "hole"; } }
An Example
Back SMYC Forward
  • The Array to Sort:
    • The six-element array (8, 4, 7, 3, 9, 3)
  • Iteration 1:
    • Sort the first two elements as follows:
    • 4 8 7 3 9 3
  • Iteration 2:
    • The 7 in element 2 is put in the proper position relative to elements 0 and 1
    • Specifically, the 4 in position 0 is left where it is, the 8 in position 1 is moved up one, and the 7 is put in the "hole" (i.e., position 1)
    • 4 7 8 3 9 3
  • Iteration 3:
    • The 3 in element 3 must be put in the proper position relative to elements 0, 1 and 2
    • Specifically, the 4, 7, and 8 are all shifted up 1 position and the 3 is put in the "hole" (i.e., position 0)
    • 3 4 7 8 9 3
  • The Remaining Iterations:
    • 3 4 7 8 9 3
      3 3 4 7 8 9
An Implementation
Back SMYC Forward
cppexamples/sorting/InsertionSort.cpp
 
Efficiency Analysis
Back SMYC Forward
  • The Outer Loop:
    • Always \(n-1\) iterations
  • The Inner Loop:
    • The worst case is when the array is in reverse order
    • In this case, the first outer loop requires 1 move, the second outer loop requires 2 moves, etc...
Efficiency Analysis (cont.)
Back SMYC Forward

\( T(n) = 1 + 2 + \cdots + (n-1) = n \cdot (n-1)/2 \)

So: \( T(n) = O(n^2) \)

There's Always More to Learn
Back -