Implementation of Selection Sort Algorithm in Python

Selection sort is a simple sorting algorithm that works by repeatedly picking the smallest element from a list and moving it to the beginning of unsorted portion of the list. In this article, we’ll explore how to implement this algorithm in Python. We’ll start with a simple implementation and then look at some practical variations, like sorting in descending order and sorting custom objects.

Prerequisites:

Basic Selection Sort Implementation

Let’s begin with a basic version of the selection sort algorithm. This code will sort a list of numbers in ascending order. We’ll go through each step, so it’s easy to follow, even if you’re just starting out with Python.

def selection_sort(arr):
  # `arr`: This is the list you want to sort
  n = len(arr)
  # `n`: This variable stores the number of items in the list

  # We go through each item in the list, except the last one
  # `range(n - 1)`: This creates a sequence of numbers from `0` to `n-2`.
  for i in range(n - 1):
    # Let's say the current item is the smallest
    # `min_index`: This will hold the index of the smallest item we find
    min_index = i

    # Now, check the rest of the list to find a smaller item
    # `range(i + 1, n)`: This sequence starts from the next item and goes to the end
    for j in range(i + 1, n):
      # If we find a smaller item
      if arr[j] < arr[min_index]:
        # Update the index of the smallest item
        min_index = j

    # If the smallest item is not the current item, swap them
    if min_index != i:
      arr[i], arr[min_index] = arr[min_index], arr[i]

  # Now the list is sorted!
  return arr

# Let's create a list
my_list = [64, 25, 12, 22, 11]

# Sort the list using selection sort
sorted_list = selection_sort(my_list)

# Print the sorted list
print("Sorted list:", sorted_list)  # Output: Sorted list: [11, 12, 22, 25, 64]

Let’s break down this code step by step:

  1. Outer Loop: The outer loop for i in range(n - 1): goes through each element in the list, except the last one. In each iteration, we assume that the current element at index i is the smallest in the unsorted part of the list. Why do we only iterate to n-2 (which is what range(n-1) gives us)? Because when we reach the second-to-last element (at index n-2), there’s only one element left to compare it with (the last element at index n-1). After this comparison and potential swap, the entire list is guaranteed to be sorted. There’s no need to consider the last element as a starting point for finding the minimum, as there would be no elements left to compare it with.

  2. Inner Loop: The inner loop for j in range(i + 1, n): checks the rest of the list to find a smaller element. If it finds one (if arr[j] < arr[min_index]:), it updates the index of the smallest element (min_index = j).

  3. Swapping: After the inner loop, we check if the smallest element is not the current element (if min_index != i:). If they are different, we swap the current element with the smallest element. This puts the smallest element in its correct position.

Sorting in Descending Order

What if we want to sort the list in descending order (from largest to smallest)? We just need to make a small change in the comparison within the inner loop. Here’s how:

def selection_sort_descending(arr):
  # `arr`: This is the list you want to sort in descending order
  n = len(arr)
  # `n`: This variable stores the number of items in the list

  # We go through each item in the list, except the last one
  for i in range(n - 1):
    # Let's say the current item is the largest
    max_index = i
    # `max_index`: This will hold the index of the largest item we find

    # Now, check the rest of the list to find a larger item
    for j in range(i + 1, n):
      # If we find a larger item
      if arr[j] > arr[max_index]:  # Note the change here: `>` instead of `<`
        # Update the index of the largest item
        max_index = j

    # If the largest item is not the current item, swap them
    if max_index != i:
      arr[i], arr[max_index] = arr[max_index], arr[i]

  # Now the list is sorted in descending order!
  return arr

# Let's create a list
my_list = [64, 25, 12, 22, 11]

# Sort the list in descending order using selection sort
sorted_list = selection_sort_descending(my_list)

# Print the sorted list
print("Sorted list (descending):", sorted_list)  # Output: Sorted list (descending): [64, 25, 22, 12, 11]

The only difference is in the if condition inside the inner loop: if arr[j] > arr[max_index]:. This change makes the function find the largest element instead of the smallest.

Sorting Custom Objects

Selection sort isn’t just for numbers; it can also sort custom objects. Suppose you have a list of dictionaries, each representing a person with a name and an age. You can sort this list based on either the name or the age. Let’s see how to do it.

def selection_sort_custom(arr, key):
  # `arr`: The list of custom objects (e.g., dictionaries) to sort.
  # `key`: A function to extract the comparison value from each object.
  n = len(arr)
  # `n`: This variable stores the number of items in the list

  for i in range(n - 1):
    min_index = i
    for j in range(i + 1, n):
      # Use the key function to get the value to compare
      if key(arr[j]) < key(arr[min_index]):
        min_index = j

    if min_index != i:
      arr[i], arr[min_index] = arr[min_index], arr[i]

  return arr


# Let's create a list of dictionaries
people = [
  {'name': 'Alice', 'age': 30},
  {'name': 'Bob', 'age': 25},
  {'name': 'Charlie', 'age': 35}
]

# Sort by age
sorted_by_age = selection_sort_custom(people.copy(), key=lambda person: person['age'])
# `people.copy()`: creates a copy of list of dictionaries.
# `key=lambda person: person['age']`: This tells the function to sort based on the 'age' key.

# Sort by name
sorted_by_name = selection_sort_custom(people.copy(), key=lambda person: person['name'])
# `key=lambda person: person['name']`: This tells the function to sort based on the 'name' key.

# Print the sorted lists
print("Sorted by age:", sorted_by_age)
# Output: Sorted by age: [{'name': 'Bob', 'age': 25}, {'name': 'Alice', 'age': 30}, {'name': 'Charlie', 'age': 35}]
print("Sorted by name:", sorted_by_name)
# Output: Sorted by name: [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}, {'name': 'Charlie', 'age': 35}]

In this example, the selection_sort_custom function takes an additional key argument. This key argument should be a function that tells the sort function how to compare the objects.

  • Sorting by Age: When sorting by age, key=lambda person: person['age'] tells the function to use the age value of each dictionary for comparison.
  • Sorting by Name: Similarly, when sorting by name, key=lambda person: person['name'] tells the function to use the name value for comparison.

This approach makes selection sort very flexible, allowing you to sort lists of any type of objects based on any criteria you define. Just pass the appropriate key function.

What’s Next?

Now that you’ve learned how to implement selection sort in Python, you can explore further: