Selection Sort: Algorithm explained with Python Code Example

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.

In this Algorithm tutorial, you will learn:

• What is Selection Sort?
• How does selection sort work?
• Problem Definition
• Solution (Algorithm)
• Visual Representation
• Selection Sort Program using Python 3
• Code Explanation
• Time Complexity Of Selection Sort
• When to use selection sort?
• Advantages of Selection Sort
• Disadvantages of Selection Sort

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.

[21,6,9,33,3]

The above list should be sorted to produce the following results

[3,6,9,21,33]

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 21 is compared with the rest of the values to check if it is the minimum value.

3 is the minimum value, so the positions of 21 and 3 are swapped. The values with a green background represent the sorted partition of the list.

Step 2)

The value 6 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

The value 6 is the minimum value, so it maintains its position.

Step 3)

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

The value 9 is the minimum value, so it maintains its position in the sorted partition.

Step 4)

The value 33 is compared with the rest of the values.

The value 21 is lower than 33, so the positions are swapped to produce the above new list.

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 3

The following code shows the selection sort implementation using Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Run the above code produces the following results

[3, 6, 9, 21, 33]

Code Explanation

The explanation for the code is as follows

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.

Time Complexity Of Selection Sort

The sort complexity is used to express the number of execution times it takes to sort the list. The implementation has two loops.

The outer loop which picks the values one by one from the list is executed n times where n is the total number of values in the list.

The inner loop, which compares the value from the outer loop with the rest of the values, is also executed n times where n is the total number of elements in the list.

Therefore, the number of executions is (n * n), which can also be expressed as O(n²).

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 [Big-O] O(n²)
• Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as [Big-Omega] Ω(n²)
• Average case – this occurs when the list is in random order. The average complexity is expressed as [Big-theta] ⊝(n²)

The selection sort has a space complexity of O(1) as it requires one temporal variable used for swapping values.

When to use selection sort?

The selection sort is best used when you want to:

• You have to sort a small list of items in ascending order
• When the cost of swapping values is insignificant
• It is also used when you need to make sure that all the values in the list have been checked.

Advantages of Selection Sort

The following are the advantages of the selection sort

• It performs very well on small lists
• It is an in-place algorithm. It does not require a lot of space for sorting. Only one extra space is required for holding the temporal variable.
• It performs well on items that have already been sorted.

Disadvantages of Selection Sort

The following are the disadvantages of the selection sort.

• It performs poorly when working on huge lists.
• The number of iterations made during the sorting is n-squared, where n is the total number of elements in the list.
• Other algorithms, such as quicksort, have better performance compared to the selection sort.

Summary:

• Selection sort is an in-place comparison algorithm that is used to sort a random list into an ordered list. It has a time complexity of O(n²)
• The list is divided into two sections, sorted and unsorted. The minimum value is picked from the unsorted section and placed into the sorted section.
• This thing is repeated until all items have been sorted.
• Implementing the pseudocode in Python 3 involves using two for loops and if statements to check if swapping is necessary
• The time complexity measures the number of steps required to sort the list.
• The worst-case time complexity happens when the list is in descending order. It has a time complexity of [Big-O] O(n²)
• The best-case time complexity happens when the list is already in ascending order. It has a time complexity of [Big-Omega] Ω(n²)
• The average-case time complexity happens when the list is in random order. It has a time complexity of [Big-theta] ⊝(n²)
• The selection sort is best used when you have a small list of items to sort, the cost of swapping values does not matter, and checking of all the values is mandatory.
• The selection sort does not perform well on huge lists
• Other sorting algorithms, such as quicksort, have better performance when compared to the selection sort.