Selection sort in Python

Selection sort is a simple comparison-based sorting algorithm. It is relatively inefficient compared to other sorting algorithms making it not suitable for sorting large sets of data. However, understanding how it works is a foundational step for understanding more sophisticated sorting algorithms and generally how sorting algorithms operates.

This algorithm has an average and worst time complexities of O(n²) where n is the number of elements in the array/list.

Selection sort works in-place meaning that it reorders the elements in the original list rather than creating a new list. This makes it memory-efficient.

Algorithm Description

In selection sort, an array/list is divided into two segments; the sorted segment on the left and the unsorted segment on the right. Initially, the sorted segment is empty while the unsorted segment consists of the entire list. At each step, the algorithm selects the smallest unsorted element and exchanges it with the first element of the unsorted segment. This gradually increases the size of the sorted segment while reducing that of the unsorted segment and eventually the entire list becomes sorted.

The algorithm can be achieved through the following steps:

Set MIN to position 0.
Find the smallest element in the list.
Swap it with the value at MIN.
Increment MIN.
Repeat steps 1-4 until the list is sorted.

Example

Consider if we start with the following unsorted list.

Elements in the sorted segment are in color green while those in the unsorted segment are in red.Two upper arrows will be used to indicate a swap operation.

At first step, the unsorted segment consists of the entire list. The MIN pointer is at the beginning of the list where the value is 4, the smallest value in the list is 0, so need to swap 4 and 0.

In the above step 0 and 4 are swapped. The sorted segment now contains a single element. In the next step, the smallest unsorted element is 1, so we need to swap it with the value at the second position which is 6.

And we go on like that with the next pairs i. 6 and 3.

The sorted segment is becoming larger while the unsorted segment is diminishing.

In the above step, 4 is already sorted so we just move to the next element.

And finally, after the last step, the list is now sorted.

Selection sort implementation

The selection sort algorithm can be implemented with nested loops.

with for loops

def selection_sort(lst):
  for i in range(len(lst)):
    smallest = i

    for j in range(i + 1, len(lst)):
      if lst[j] < lst[smallest]:
        smallest = j

    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
selection_sort(L)

print("The sorted list is: ", L)

In the above implementation, the sorted segment of the list starts at 0 and ends at i while the unsorted segment starts at i + 1 and ends at n-1 where n is the length of the list.

The outer loop traverses through all elements of the list. While inner loop's only traverses the unsorted segment (beginning at i.e i + 1 ) , it finds the position of the smallest unsorted element and assigns it to the smallest variable. The smallest element is then swapped with the outer loops current value in the lst[i], lst[smallest] = lst[smallest], lst[i] statement.

with nested while loops

We can also implement the selection sort algorithm using nested while loops, as shown below:

def selection_sort(lst):
  i = 0
  while i < len(lst):

    smallest = i
    j = i + 1
    while j < len(lst):
      if lst[j] < lst[smallest]:
        smallest = j
      j += 1
    
    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements
    i += 1

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

selection_sort(L)
print("The sorted list is: ", L)

Descending selection sort

To make the selection sort algorithm to sort the elements in descending order, we simply need to change the sign from < to > in the comparison line i.e from if lst[j] < lst[smallest]: . to if lst[j] > lst[smallest]: .This is as shown below:

#descending selection sort
def selection_sort(lst):
  for i in range(len(lst)):
    smallest = i

    for j in range(i + 1, len(lst)):
      if lst[j] > lst[smallest]:
        smallest = j

    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
selection_sort(L)

print("The sorted list is: ", L)

Complexity Analysis

space complexity

The selection sort algorithm has a space complexity of O(1) . This means that it is memory-efficient as it does extra extra memory except for holding the basic variables e.g smallest.

time complexity

The presence of nested loops in the selection sort algorithm implies that it has a time complexity of O(n²), this is for both average case and worst case scenarios.

Blog

Selection sort in Python

Main