Skip to main content

Section 8.5 Selection Sort

S election sort works by splitting a list into two portions - a sorted part and an unsorted part. Initially, everything is in the unsorted part, but one card at a time, we select the smallest remaining unsorted item and move it to the beginning of the unsorted portion, thereby making it sorted.
Put into an algorithm for a human to sort a hand of playing cards, it might look like this: 
1   Get a hand of unsorted cards
2   Set a marker for the unsorted section at the front of the hand
3   Repeat 4-7 until one card remains in the unsorted section
4       Compare all unsorted cards
5       Select the smallest unsorted card
6       Swap this number with the first card in the unsorted section
7       Advance the marker to the right one card
8   Stop
To see how the Selection Card Sort Algorithm works, watch the video below. As the sort progresses, the appropriate step of the algorithm will be highlighted in the bottom left panel of the animation. To divide the sorted and unsorted sections of our hand, we use a black vertical bar. On each loop through steps 4-7, we will keep track of the current cards we are comparing by pointing to them with a pair of human hands. The left hand will point to the smallest card we have seen so far, and the right hand will point to the card currently being considered.
Animation used by permission of Virginia Tech

Checkpoint 8.5.2.

What does selection sort do during each pass through its unsorted portion?
  • Find the smallest remaining item and move it to the front of the unsorted portion.
  • Swap every adjacent pair in the list.
  • Split the list into halves and merge them.
  • Choose a random item as the next sorted value.

Checkpoint 8.5.3.

As selection sort proceeds, what is true of the portion before the marker?
  • It is sorted and contains the smallest items found so far.
  • It is unsorted and never changes.
  • It contains only the largest items.
  • It is empty until the final pass.

Checkpoint 8.5.4.

We do a selection sort (using min value to front strategy) on the list 3, 2, 4, 5, 1. Arrange the blocks below to show the state of the list after each pass of the algorithm.
Note that you may use the same block twice in a row if the current pass does not change the list.
You will not use all of the blocks.
You have attempted of activities on this page.
PrevTopNext