how the Selection Sort works, let's
see how the computer would perform this sort with numbers. Below is
our modified algorithm for sorting a list of numbers.
Selection Sort Algorithm
- Get a list of unsorted numbers
- Set a marker for the unsorted section at the front of the list
- Repeat steps 4 - 6 until one number remains in the unsorted
section
- Compare all unsorted numbers in order to select
the smallest one
- Swap this number with the first number in
the unsorted section
- Advance the marker to the right one position
- Stop
|
Again our modified algorithm is almost identical to our card sorting
algorithm. We only needed to substitute numbers for playing cards and
a list of numbers for a hand of cards. One other slight change is that
steps 4 and 5 of the Selection Card Sort have been combined. This is
typical since a computer will usually keep track of the smallest number
while it compares all the numbers. The steps below illustrate how the
Selection Sort algorithm works on a computer.
- First, we give the computer a list of unsorted numbers and store them
in an array of memory cells.
- To begin the sort, the computer divides the sorted and unsorted sections
of the list by placing a marker before the first number. To sort the
numbers, the computer will repeatedly search the unsorted section for
the smallest number, swap this number with the first number in the unsorted
section, and update the sort marker.
- To find the smallest number in the unsorted section, the computer
must make six comparisons: (7 < 8), (7 > 5),
(5 > 2), (2 < 4), (2 < 6), and
(2 > 3). After these comparisons, the computer knows that
2 is the smallest number, so it swaps this number with 7, the first
number in the unsorted section, and advances the sort marker.
- Now five more comparisons are needed to find the smallest number in
the unsorted section: (8 > 5), (5 < 7), (5 > 4),
(4 < 6), and (4 > 3). After these comparisons,
the computer swaps 3, the smallest number in the unsorted section, with
8, the first number in the unsorted section, and advances the sort marker.
- This time four comparisons are needed to determine that 4 is the
smallest number in the unsorted section: (5 < 7), (5 > 4),
(4 < 6), and (4 < 8). After these comparisons,
the computer swaps 4 with 5 and then advances the sort marker.
- After three more comparisons, the computer identifies 5 as the smallest
unsorted number: (7 > 5), (5 < 6), and (5 < 8).
Then the computer swaps 5 with 7 and advances the sort marker.
- This time only two comparisons are needed to determine that 6 is the
smallest number: (7 > 6) and (6 < 8). After
these two comparisons, the computer swaps 6 with 7 and then advances
the sort marker.
- Now we only need a single comparison to find the right position for
7: (7 < 8). Since 7 is the smallest number and it is also
the first number in the unsorted section, the computer does not need
to swap this number. It only needs to advance the sort marker. Now there
is only one number in the unsorted section, so the list of numbers is
sorted and the Selection Sort algorithm is complete.
Resource Link: https://courses.cs.vt.edu/csonline/Algorithms/Lessons/SelectionSort/index.html