Teaching Kids Programming – Selection Sort Implementation in Python (Simple Sorting Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

The selection sort is another simple sorting algorithm. Similar to Bubble sorting, it separates the list into two sub arrays: sorted and unsorted.

For selection sort, the left subarray (at the begining zero) is sorted, and the right subarray is unsorted. Each round, we find the element with the smallest value in the unsorted sub array and then swap it to the beginning of the unsorted subarray. And then we have one more sorted element and one less element to sort.

1
2
3
4
5
6
7
8
9
10

Sorted: [] Unsorted: [3, 5, 2, 6, 1, 3, 4, 6, 9] // min = 1 in the Unsorted
Sorted: [1, ] Unsorted: [3, 5, 2, 6, 3, 4, 6, 9] // min = 2 in the Unsorted
Sorted: [1, 2] Unsorted: [3, 5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted
Sorted: [1, 2, 3] Unsorted: [5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted
Sorted: [1, 2, 3, 3] Unsorted: [5, 6, 4, 6, 9] // min = 4 in the Unsorted
Sorted: [1, 2, 3, 3, 4] Unsorted: [5, 6, 6, 9] // min = 5 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5] Unsorted: [6, 6, 9] // min = 6 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5, 6] Unsorted: [6, 9] // min = 6 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5, 6, 6] Unsorted: [9] // min = 9 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5, 6, 6, 9] Unsorted: [] // Done.

Sorted: [] Unsorted: [3, 5, 2, 6, 1, 3, 4, 6, 9] // min = 1 in the Unsorted
Sorted: [1, ] Unsorted: [3, 5, 2, 6, 3, 4, 6, 9] // min = 2 in the Unsorted
Sorted: [1, 2] Unsorted: [3, 5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted
Sorted: [1, 2, 3] Unsorted: [5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted
Sorted: [1, 2, 3, 3] Unsorted: [5, 6, 4, 6, 9] // min = 4 in the Unsorted
Sorted: [1, 2, 3, 3, 4] Unsorted: [5, 6, 6, 9] // min = 5 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5] Unsorted: [6, 6, 9] // min = 6 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5, 6] Unsorted: [6, 9] // min = 6 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5, 6, 6] Unsorted: [9] // min = 9 in the Unsorted
Sorted: [1, 2, 3, 3, 4, 5, 6, 6, 9] Unsorted: [] // Done.

Selection Sorting Algorithm (Python)

When the array is already sorted, the improved bubble sorting algorithm can terminate earlier and thus in the best case, the time complexity is O(N) for an improved bubble sorting. However, for selection sorting, the time complexity is always O(N^2) quadratic.

But there is one advantage for selection sort, the number of swaps is N times – but for bubble sorting, the number of swaps could be in the scale of O(N^2) considering the reversed sorted array such as [5, 4, 3, 2, 1] – each bubbling will only move a large element to the end with N swaps, and there are N numbers to move.

1
2
3
4
5
6
7
8
9
10
11

def selectionSort(nums):
    n = len(nums)
    for i in range(n): 
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        # Swap the found minimum element with # the first element       
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

def selectionSort(nums):
    n = len(nums)
    for i in range(n): 
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        # Swap the found minimum element with # the first element       
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

If the index of min is equal to the first element (i.e. the first element in the unsorted sublist is the min), then we don’t need to swap:

1
2
3
4
5
6
7
8
9
10
11
12

def selectionSort(nums):
    n = len(nums)
    for i in range(n): 
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        # Swap the found minimum element with # the first element if it is different
        if min_idx != i:
            nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

def selectionSort(nums):
    n = len(nums)
    for i in range(n): 
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        # Swap the found minimum element with # the first element if it is different
        if min_idx != i:
            nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

With this check, the number of swaps will be no more than N. and in best cases, no swap is made – when all elements are in order.

Selection sort is not stable – as it might break the order of the keys with same values. For example: [3, 2, 3′, 1] after first round of Selection Sort, the 1 is swapped with the first 3, so the array becomes [1, 2, 3′, 3]. The [3, 3′] becomes [3′, 3] – hence not stable.

Sorting Algorithms (Teaching Kids Programming Tutorials)

• Teaching Kids Programming – Bubble Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – MergeSort Simply Explained
• Teaching Kids Programming – QuickSort Algorithm Simply Explained
• Teaching Kids Programming – Selection Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)
• Teaching Kids Programming – Counting Sort Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —