Selection Sort Algorithm: Pseudocode and Implementation Details

In the previous article, we explored how selection sort works by walking through a step-by-step example. Now, let’s go through the algorithmic details and examine the pseudocode implementation of selection sort. By the end of this article, you’ll have an understanding of how to translate this sorting algorithm into actual code.

Before you proceed, it would be beneficial to read these articles:

Understanding the Key Concepts

Selection sort is an intuitive sorting algorithm that works by dividing the array into two portions: sorted and unsorted. It gradually builds the sorted portion by repeatedly finding the smallest (or largest) element from the unsorted portion and placing it at the end of the sorted portion. Before we look into the algorithm and pseudocode of selection sort, let’s quickly recap the key concepts:

  • Unsorted Portion - The part of the array that hasn’t been sorted yet. The algorithm repeatedly finds the smallest element in this portion and adds it to the end of the sorted portion.

  • Sorted Portion - The part of the array that is already sorted. With each iteration, this portion grows element by element. Initially this starts as empty.

  • Current Position - The position where we’ll place the next smallest element. It starts from the beginning of the array and moves right after each iteration. This can also be thought as the starting position of the unsorted portion of the array.

  • Minimum Element - The smallest element found in the unsorted portion. We keep track of its index as we scan through the array.

  • Swapping - The operation of exchanging the minimum element with the first element in the unsorted portion, which places it in its correct sorted position.

Algorithm for Selection Sort

Here is a simple breakdown of the selection sort algorithm:

  1. Start with Unsorted Array: Begin by considering the entire array as unsorted, with no elements in the sorted portion yet.

  2. Find Minimum Element: Scan through the unsorted portion to identify the smallest element and remember its position.

  3. Swap Elements: Exchange the smallest element you found with the first element in the unsorted portion, effectively placing it at the beginning of the sorted portion.

  4. Update Boundaries - Move the dividing line between sorted and unsorted portions one position to the right, expanding the sorted section.

  5. Repeat Process - Continue finding the minimum element, swapping, and updating boundaries (Steps 2-4) until the entire array becomes sorted.

Pseudocode for Selection Sort

Here’s the pseudocode that represents the iterative approach of the selection sort algorithm:

def selection_sort(array):
  n = len(array)

  # Loop through each element in the array
  for i in range(n - 1):
    # Assume the current index has the minimum value
    min_index = i

    # Check every following element to see if it's smaller
    for j in range(i + 1, n):
      if array[j] < array[min_index]:
        # If a smaller value is found, update the index of the minimum value
        min_index = j

    # After finding the smallest value, swap if needed
    if min_index != i:
      array[i], array[min_index] = array[min_index], array[i]

Explanation of the Pseudocode

Let’s break down the pseudocode step by step:

  • def selection_sort(array): This line defines the function named selection_sort, which takes an array as input.
  • n = len(array): Here, n stores the number of elements in the input array.
  • for i in range(n - 1): This outer loop iterates from the first element (0) to the second-to-last element (n - 2). We stop at n - 2 because the last element will automatically be in its correct position after the n - 1 element is sorted.
  • min_index = i: We assume that the current element at index i is the minimum element in the unsorted portion of the array. We store its index in min_index.
  • for j in range(i + 1, n): This inner loop iterates through the unsorted portion of the array, starting from the element next to the current one (i + 1) to the last element (n - 1).
  • if array[j] < array[min_index]: We compare each element array[j] with the current minimum element array[min_index]. If we find an element smaller than the current minimum, we update min_index to the index of the new minimum element (j).
  • if min_index != i: After the inner loop completes, we check if the min_index has changed. If it has, it means we found a new minimum element in the unsorted portion.
  • array[i], array[min_index] = array[min_index], array[i]: If min_index is different from i, we swap the element at index i with the element at index min_index. This places the smallest element at its correct position in the sorted portion of the array.

Example Walkthrough

Let’s trace the iterative pseudocode with the array [64, 34, 25, 12, 22].

  1. First Iteration (i = 0):

    • Initial array: [64, 34, 25, 12, 22]
    • min_index = 0 (assume 64 is the smallest).
    • Inner loop:
      • j = 1: 34 < 64 is true, min_index = 1.
      • j = 2: 25 < 34 is true, min_index = 2.
      • j = 3: 12 < 25 is true, min_index = 3.
      • j = 4: 22 < 12 is false.
    • Swap array[0] (64) with array[3] (12): [12, 34, 25, 64, 22]

  2. Second Iteration (i = 1):

    • Current array: [12, 34, 25, 64, 22]
    • min_index = 1 (assume 34 is the smallest).
    • Inner loop:
      • j = 2: 25 < 34 is true, min_index = 2.
      • j = 3: 64 < 25 is false.
      • j = 4: 22 < 25 is true, min_index = 4.
    • Swap array[1] (34) with array[4] (22): [12, 22, 25, 64, 34]

  3. Third Iteration (i = 2):

    • Current array: [12, 22, 25, 64, 34]
    • min_index = 2 (assume 25 is the smallest).
    • Inner loop:
      • j = 3: 64 < 25 is false.
      • j = 4: 34 < 25 is false.
    • No swap needed since min_index is still 2.

  4. Fourth Iteration (i = 3):

    • Current array: [12, 22, 25, 64, 34]
    • min_index = 3 (assume 64 is the smallest).
    • Inner loop:
      • j = 4: 34 < 64 is true, min_index = 4.
    • Swap array[3] (64) with array[4] (34): [12, 22, 25, 34, 64]

After these steps, the array is now fully sorted: [12, 22, 25, 34, 64]

What’s Next?

Now that you understand the pseudocode and implementation details of selection sort, you might want to: