Lab 18 Insertion Sort

Objectives and Background

Implement the Insertion sort algorithm. Your code should read the input from the command line, as in the Selection Sort example in class, stored in main()’s args parameter. You may borrow code, such as printArr() to output the result.

The high-level idea of Insertion Sort is to logically split the input numbers into a sorted portion and an unsorted portion. The sorted portion is initially just a single item, usually the lowest index one.

Consider the pseudocode from Wikipedia (‘←’ is assignment):

i ← 1

while i < length(A)

    j ← i

while j > 0 and A[j-1] > A[j]

swap A[j] and A[j-1]

        j ← j - 1

end while

    i ← i + 1

end while

Step-by-step example

· Bold indicated items being compared

· S=Sorted, U=Unsorted. This is not “really” in the algorithm. The counter variable i marks the edge of the sorted region.

· i is the counter variable in the outer loop  (j not shown)

 Start (S=Sorted, U-Unsorted)

S	U	U	U	U
4	2	3	1	5

Round 1 (i=1)

S	U	U	U	U
4	2	3	1	5

(swap)

S	U	U	U	U
2	4	3	1	5

Round 2 (i=2)

S	S	U	U	U
2	4	3	1	5

(swap)

S	S	U	U	U
2	3	4	1	5

(don’t swap, done inserting)

Round 3 (i=3)

S	S	S	U	U
2	3	4	1	5

(swap)

S	S	S	U	U
2	3	1	4	5

(swap)

S	S	S	U	U
2	1	3	4	5

(swap)

S	S	S	U	U
1	2	3	4	5

(done inserting, at lowest index)

Round 4 (i=4)

S	S	S	S	U
1	2	3	4	5

(done, no swapping)

Final Array

S	S	S	S	S
1	2	3	4	5

(this is the same as last round, not actually in algorithm, just note that the sorted region covers the entire array)

Lab Report Question

0. (not a question, but a comment: Since you were given the pseudocode of the algorithm, you don’t need to give the pseudocode or flowchart)

1. Now that you have implemented Insertion Sort, you should be able to see that Insertion sort is quite fast on sorted or nearly sorted input. Explain why.

2. What is the worst case for insertion Sort? Specifically, what type of input causes the maximum number of swaps?