Section 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 = 0 i marks start of unsorted cards
2 repeat (length of the list - 1) 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.You have attempted 1 of 1 activities on this page.
