Selection sort

SELECTION SORT is a comparison sorting algorithm that is used to sort a random list of items in ascending order. The comparison does not require a lot of extra space. It only requires one extra memory space for the temporal variable.

By default, the sorted list is empty, and the unsorted list contains all the elements. The unsorted list is then scanned for the minimum value, which is then placed in the sorted list. This process is repeated until all the values have been compared and sorted.

How does selection sort work?

The first item in the unsorted partition is compared with all the values to the right-hand side to check if it is the minimum value. If it is not the minimum value, then its position is swapped with the minimum value.

Example:

• For example, if the index of the minimum value is 3, then the value of the element with index 3 is placed at index 0 while the value that was at index 0 is placed at index 3. If the first element in the unsorted partition is the minimum value, then it returns its positions.
• The element that has been determined as the minimum value is then moved to the partition on the left-hand side, which is the sorted list. 
• The partitioned side now has one element, while the unpartitioned side has (n – 1) elements where n is the total number of elements in the list. This process is repeated over and over until all items have been compared and sorted based on their values.

Problem Definition

A list of elements that are in random order needs to be sorted in ascending order. Consider the following list as an example.

5, 7, 2, 3, 8

The above list should be sorted to produce the following results

2, 3, 5, 7, 8.

Solution (Algorithm)

Step 1) Get the value of n which is the total size of the array

Step 2) Partition the list into sorted and unsorted sections. The sorted section is initially empty while the unsorted section contains the entire list

Step 3) Pick the minimum value from the unpartitioned section and placed it into the sorted section. 

Step 4) Repeat the process (n – 1) times until all of the elements in the list have been sorted.

Visual Representation

Given a list of five elements, the following images illustrate how the selection sort algorithm iterates through the values when sorting them.

The following image shows the unsorted list

Step 1)

The first value 5 is compared with the rest of the values to check if it is the minimum value.

2 is the minimum value, so the positions of 5 and 2 are swapped. The green values represent the sorted partition of the list.

Step 2)

The value 7 which is the first element in the unsorted partition is compared with the rest of the values to find out if a lower value exists:

3 is the minimum value, so the positions of 7 and 3 are swapped:

Step 3)

The first element of the unsorted list with the value of 5 is compared with the rest of the values to check if it is the minimum value.

Step 4)

The value 7 is compared with the rest of the values. The value 7 is the minimum value, so it maintains its position in the sorted partition.

Step 5)

We only have one value left in the unpartitioned list. Therefore, it is already sorted.

The final list is like the one shown in the above image.

Selection Sort Program using Python

The following code shows the selection sort implementation using Python

Run the above code produces the following results

Here is Code explanation:

1. Defines a function named selectionSort
2. Gets the total number of elements in the list. We need this to determine the number of passes to be made when comparing values.
3. Outer loop. Uses the loop to iterate through the values of the list. The number of iterations is (n – 1). The value of n is 5, so (5 – 1) gives us 4. This means the outer iterations will be performed 4 times. In each iteration, the value of the variable i is assigned to the variable minValueIndex
4. Inner loop. Uses the loop to compare the leftmost value to the other values on the right-hand side. However, the value for j does not start at index 0. It starts at (i + 1). This excludes the values that have already been sorted so that we focus on items that have not yet been sorted.
5. Finds the minimum value in the unsorted list and places it in its proper position
6. Updates the value of minValueIndex when the swapping condition is true
7. Compares the values of index numbers minValueIndex and i to see if they are not equal
8. The leftmost value is stored in a temporal variable
9. The lower value from the right-hand side takes the position first position
10. The value that was stored in the temporal value is stored in the position that was previously held by the minimum value
11. Returns the sorted list as the function result
12. Creates a list el that has random numbers
13. Print the sorted list after calling the selection Sort function passing in el as the parameter.

The largest-so-far value, again initially the first number, must be compared to all the other numbers in the unsorted
part of the list, which will require \(n-2\) comparisons. The number of comparisons keeps decreasing as the length of the unsorted section of the list gets smaller, until finally only one comparison is needed. The total number
of comparisons is

\((n-1)+(n-2)+(n-3)+ \ldots + 3+2+1= \frac{(n-1) n}{2}=\frac{n^2-n}{2} \)

The selection sort algorithm not only does comparisons, it does exchanges. Even if the largest number in the unsorted section of the list is already at the end of the unsorted section, the algorithm exchanges this number with itself.
Therefore, the algorithm does \(n\) exchanges, one for each position in the list to put the correct value in that position. However, the work contributed by exchanges and marker moving is so much less than the amount contributed by comparisons that it can be ignored.

Therefore, the number of executions is \(n^2\), which can also be expressed as \(O\left(n^2\right)\).

The selection sort has three categories of complexity namely:

• Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as \(O\left(n^2\right)\)
• Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as \(\Omega\left(n^2\right)\)
• Average case – this occurs when the list is in random order. The average complexity is expressed as \(\Theta\left(n^2\right)\)