8.6. Selection Sort Code

Turning the selection sort into an algorithm for a computer requires a little more detail than the version a human can use to sort cards. The basic strategy is the same, but instead of a marker and two hands, we need to use variables to store locations in the list that we care about.

In the code below, i is equivalent to the black line - it marks the start of the unsorted portion of the list. j is the right hand - it stores the location we are at as we scan for the next smallest card. Finally, currentMinIndex is the left hand - it remembers where the smallest value we have seen is as we sweep through the unsorted part of the list. Also, recall that list[j] means “the value in the list at location j”.

Don’t worry about memorizing the algorithm, but do refer to it as you use the animation below.

    Note: assume that list already exists
1   i = 1                                    i marks start of unsorted cards
2   repeat (length of the list) times:
3       currentMinIndex = i                 curentMinIndex is the "left hand"
4       currentMin = list[currentMinIndex]  smallest value seen so far
5       j = i                               j is the "right hand"
6
7       Note: find smallest remaining card
8       repeat while j <= (length of list)
9           if list[j] < currentMin
10              Note: New smallest card - move "left hand"
11              currentMinIndex = j
12              currentMin = list[j]
13          j = j + 1                       shift "right hand"
14
15      Swap smallest unsorted with first unsorted
16      list[currentMinIndex] = list[i]
17      list[i] = currentMin
18
19      i = i + 1                           move start of unsorted one to right

The animation below allows you to step through a selection sort. Each step either advances the “right hand” or does a swap and then advances the “marker”. Step through some sorts and refer to the algorithm above until you see how i, j, and currentMin are being used to keep track of locations in the list and can predict the outcome of steps before clicking the button.

Step Reset Reset - Partial Sorted

Animation based on work by Y. Daniel Liang

You have attempted of activities on this page