Selection sort in Python

Introduction

Selection sort is a simple in-place (i.e. no auxiliary memory) comparison based sorting algorithm. It is an inefficient algorithm with O(n2) running time as it uses two nested loops.

Here is a summary of steps how the algorithm works:

  • Given an unsorted list
  • Start with the first element on the left side
  • Scan all other elements on the right side and find the smallest
  • Swap the smallest element with the first element if they are not equal
  • Now the first element is the smallest
  • Go to the second element, scan all elements to the right, find the smallest
  • Swap the smallest with the second element
  • Repeat these steps until all elements are sorted

Here is a cool Gypsy folk dance YouTube video demonstrating selection sort visually:

Selection sort python code

Here is an example Python source code:

# Example input list
A = [4, 2, 1, 0, -1]

# Number of items in the list
n = len(A)

# Outer loop index (i) goes from (0) to (n-1)
for i in range (n-1):
    # Assume the element at (i) 
    # is the smallest in the list
    minj = i

    # Scan all elements to the right of (i) 
    # and find the smallest
    for j in range(i+1, n):
        if A[j] < A[minj]:
            minj = j

    # Swap the smallest element to the right 
    # of (i) with the element at (i) unless 
    # they are equal
    if minj != i: 
        x = A[i]
        A[i] = A[minj]
        A[minj] = x

# Print the sorted array
print (A)

Thanks for reading. For questions or feedback, please the comments section below.

Leave a Reply