Page 218 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

Notes
Figure 13.1: Insertion Sort

Source: http://ee.sjtu.edu.cn/po/Class-web/data-stucture/csc120ch9.pdf
On average, there are n /4 + O(n) = O(n ) for both the number of comparisons of keys and the
2
2
number of assignments of entries. For the best case, there are (n–1) comparisons which is of O(n)
because they have already been sorted.
Now let us see the step by step example:

Example: Having the following list, let’s try to use insertion sort to arrange the numbers
from lowest to greatest:
Unsorted list: 6 4 5 10 3 1 8 9 7 2
Step 1:
4 6 5 10 3 1 8 9 7 2 – As 6 was the first element, at step 1, the element 4 is being inserted, and 4 is
smaller than 6, so it must place before 6, so the order would be 4 6.
Step 2:
4 5 6 10 3 1 8 9 7 2 – At step 2, 5 was the element to be inserted, and being smaller than 6, it goes
before it, but then it is compared to 4 which is smaller than 5, now the order would be 4 5 6.
Step 3:
4 5 6 10 3 1 8 9 7 2 – At step 3, 10 was the new element, and being greater than 6, the element was
in the right place and no moving had to take place, now the order would be 4 5 6 .
Step 4:
3 4 5 6 10 1 8 9 7 2 – At step 4, 3 was the new element, and compared to 10 it is smaller, so it has
to move to the left, also, it is compared to 6 then to 5 and then to 4, and is smaller than any of
these, so the position of the element 3 is at the left of all these numbers, now the order would be
3 4 5 6.

LOVELY PROFESSIONAL UNIVERSITY 211