Also see: Additional Discussion
on InsertionSort
| Date Assigned: | Fri Nov-17 |
| Date Due: | Mon Nov-20 |
0. Notes:
a) There will be a quiz on Tuesday covering selectionSort (from
last assignment), insertionSort, and bubbleSort (which we will cover in
class on Monday).
b) You may not work with others on this assignment.
c) Good luck!
1. Modify Assignment 20 so that is uses insertionSort() instead of selectionSort().
But... what is insertionSort?
InsertionSort, like selectionSort (which we already know), moves a cursor from left-to-right across the vector. Here, rather than find the smallest element to the right of the cursor, however, we always use the element immediately to the right of the cursor, and we insert that element in a sorted order into the elements to the left of the cursor. Here is a sample to clarify:
cursor: 3 8 2 9 5 1 7 6Notice in the last iteration that the 2 moved to the front of the sorted elements because it is less than 3, then 3 and 8 were shifted over one to the right to make room for 2.
^
|
+-------+
|
v
3 cursor: 8 2 9 5 1 7 6
^
|
+------+
|
v
3 8 cursor: 2 9 5 1 7 6
^
|
+-------------+
|
v
2 3 8 cursor: 9 5 1 7 6
This description is intentionally left somewhat sparse. There is enough information here for you to write insertionSort, though you may need to, as Winnie the Pooh would put it: Think, think, think.
Good luck, and have a splendid weekend.
DK