Selection Sort Exploration

We will start by watching selection sort run slowly on a reasonably small data set. When you watch it, look for these things:

• where do you see the sorting first?
• what values are i and j taking on?
• how does max_pos move through the array?
• do you see the biggest unsorted item moving into its position?
• do you see the effect of the swap?

Record the number of swaps and comparisons reported and run it again with the same parameters:

Did the number of comparisons or swaps change? Why or why not?

Now run it using the same amount of data, but with sorted and reversely sorted input and record the number of swaps and comparisons:

Did the number of comparisons or swaps change? Why or why not?

Clearly, the run-time of the algorithm on sorted data is not zero and it still changes with the size of the input. This tells us that counting the number of swaps does not give us a good measure of the run-time of Selection Sort. Since the comparisons are not affected by the data, comparisons gives us a better measure of run-time.

To get a feel for how the run-time changes with the size of the input, make the following runs. Remember that elapsed time is not an accurate measure, but it will give you a feel for the magnitude of the changes in run-time. For a more accurate measure, record the number of comparisons made for each input and graph your results.

Here is a chart with the results: