## Description

Insertion Sort vs. Selection Sort

Implement Insertion Sort (as discussed in class) and Selection Sort (as described below). You can use

one of the following programming languages: C/C++, Java or Python.

Selection Sort

Selection Sort is the following algorithm. Given an array A[1 . . . n] you first find the smallest element

in A and exchange it with A[1]. Then find the second smallest element in A and exchange it with A[2].

Continue this for the first n − 1 elements of A (See CLRS Exercise 2.2-2).

Input/Output:

Your input will be a sequence of n numbers x1, x2, . . . , xn given in an input file in this order. Each number will

be an integer between 1 and n. The output should be a file containing these integers sorted in non-decreasing

order.

For each of the first 4 input types below you should plot the running time of each algorithm for inputs

of size n = 5000, 10000, 15000, . . . up to 30000. Plot both algorithms on the same chart so that it is easy

to compare. For the last input type (small random inputs) see instructions below. When measuring the

running time you should only measure the time of sorting, not the time spent generating the data.

Input/Plot 1: Large random inputs. Generate each xi to be a uniformly random integer between

1 and n. On random inputs that you generate: For each data point take the average of 3 runs (each time

generating a new random input).

Input/Plot 2: Non-decreasing inputs. Generate each xi to be a uniformly random integer between

1 and n and sort the resulting sequence in non-decreasing order (x1 ≤ x2 ≤ . . . ≤ xn). Then run each of the

sorting algorithms again and measure its performance.

1

Input/Plot 3: Non-increasing inputs. Generate each xi to be a uniformly random integer between

1 and n and sort the resulting sequence in non-increasing order (x1 ≥ x2 ≥ . . . ≥ xn). Then run each of the

sorting algorithms again and measure its performance.

Input/Plot 4: Noisy non-decreasing inputs. Generate input in two steps:

1. Generate input as in Plot 2.

2. Repeat the following 50 times: Pick two random integers i and j and exchange xi and xj .

For each data point take the average of 3 runs (each time generating a new random input).

Input 5: Small random inputs. Generate 100,000 inputs as in Input/Plot 1 for n = 50. Measure

the overall runtime of sorting these inputs. There is no plot for this type of input, just compare the two

resulting runtimes.

Write-up

Explain your choices: Explain any platform/language choices that you made for your code and plots.

How did you create and store the data you used to make the plots. Did you run into any difficulties or made

any interesting observations?

Conclusions: Both of these algorithms have asymptotic quadratic running time (O(n

2

)). Does the first

plot reflect this? How do the two algorithms compare in terms of the running time? How about the second

plot? Do you think this one is quadratic? Why do you think it looks the way it does? How does the third

plot compare to the first and second? What about the fourth plot? Would you use these algorithms for real

data and if so why?

2