Selection Sort

Selection sort is a very simple and inefficient sorting algorithm which sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

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.

Here is an algorithm from p216 for the bubble sort in pseudocode:

//p216 Example 23:selection sort

//==== Selection Sort ================

output "Selection sort algorithm"

output ""

ELEMENTS = [1,5,3,86,256,420,9,510,51,24,60]

MIN = 0

LEAST = 0

TEMP = 0

output "Before sorting"

output ELEMENTS

output ""

loop MIN from 0 to 10

    LEAST = MIN

    loop CURRENT from MIN+1 to 10

        if ELEMENTS[CURRENT] < ELEMENTS[LEAST] then

           LEAST = CURRENT

        end if

    end loop    

    TEMP = ELEMENTS[LEAST]

    ELEMENTS[LEAST] = ELEMENTS[MIN]

    ELEMENTS[MIN] = TEMP

end loop

output "After sorting"

output ELEMENTS

Exercises

1. Download p216Ex23 and load it into Mr Mulkey's p-code tool.

2. Convert p216 Ex23 into a similar version using Functions in Python 3 using codeskulptor3 or Visual Studio Code.  

3. Run your final Python 3 program in the visualizer from Pythontutor   (SelectioSort-codeskulptor3)

Further reading/activities

• Interactivepython - Selection Sort

• Selection Sort Interactive trace activity - Interactive activity that randomly generates sets of values. You need to trace the use of the selection sort algorithm to sort the values.

Selection sort vs Bubble sort - GeekforGeeks