Python Program for Selection Sort with Example and Explanation

A Python program for selection sort uses nested loops to repeatedly find the smallest element and swap it with the current position, like for i in range(len(arr)): min_idx = i; for j in range(i+1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j; arr[i], arr[min_idx] = arr[min_idx], arr[i].

Examples

Input[5, 3, 8, 6, 2]

Output[2, 3, 5, 6, 8]

Input[1, 2, 3, 4, 5]

Output[1, 2, 3, 4, 5]

Input[]

Output[]

How to Think About It

To sort a list using selection sort, you look at each position one by one and find the smallest number from the rest of the list. Then, you swap that smallest number with the number at the current position. You repeat this until the whole list is sorted.

Algorithm

1

Start from the first element of the list.

2

Find the smallest element in the unsorted part of the list.

3

Swap the smallest element found with the element at the current position.

4

Move to the next position and repeat until the list is fully sorted.

Code

python

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example usage
numbers = [5, 3, 8, 6, 2]
selection_sort(numbers)
print(numbers)

Output

[2, 3, 5, 6, 8]

Dry Run

Let's trace the list [5, 3, 8, 6, 2] through the selection sort code.

1

Start with i=0

Find smallest from index 0 to end: smallest is 2 at index 4. Swap arr[0] and arr[4]. List becomes [2, 3, 8, 6, 5].

2

i=1

Find smallest from index 1 to end: smallest is 3 at index 1. Swap arr[1] and arr[1] (no change). List stays [2, 3, 8, 6, 5].

3

i=2

Find smallest from index 2 to end: smallest is 5 at index 4. Swap arr[2] and arr[4]. List becomes [2, 3, 5, 6, 8].

4

i=3

Find smallest from index 3 to end: smallest is 6 at index 3. Swap arr[3] and arr[3] (no change). List stays [2, 3, 5, 6, 8].

5

i=4

Only one element left, no action needed.

i	min_idx	List after swap
0	4	[2, 3, 8, 6, 5]
1	1	[2, 3, 8, 6, 5]
2	4	[2, 3, 5, 6, 8]
3	3	[2, 3, 5, 6, 8]
4	4	[2, 3, 5, 6, 8]

Why This Works

Step 1: Find the smallest element

The inner loop looks through the unsorted part of the list to find the smallest element using if arr[j] < arr[min_idx].

Step 2: Swap with current position

Once the smallest element is found, it swaps places with the element at the current index i to move it to its correct sorted position.

Step 3: Repeat for all elements

The outer loop moves the current position forward, repeating the process until the entire list is sorted.

Alternative Approaches

Bubble Sort

python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

numbers = [5, 3, 8, 6, 2]
bubble_sort(numbers)
print(numbers)

Bubble sort repeatedly swaps adjacent elements and is simpler but usually slower than selection sort.

Built-in sort()

python

numbers = [5, 3, 8, 6, 2]
numbers.sort()
print(numbers)

Python's built-in sort is highly optimized and faster than selection sort for most cases.

Complexity: O(n^2) time, O(1) space

Time Complexity

Selection sort uses two nested loops each running up to n times, resulting in O(n^2) time complexity regardless of input order.

Space Complexity

It sorts the list in place, so it uses only a constant amount of extra space, O(1).

Which Approach is Fastest?

Built-in sort is fastest due to optimized algorithms; selection sort is simple but slower, and bubble sort is usually slower than selection sort.

Approach	Time	Space	Best For
Selection Sort	O(n^2)	O(1)	Small lists, learning sorting basics
Bubble Sort	O(n^2)	O(1)	Very simple implementation, educational
Built-in sort()	O(n log n)	O(n)	Real-world sorting, large data