Sorting — Selection Sort

Python Data Structures and Algorithms — Day 1

Introduction

Selection Sort is a simple comparison-based sorting algorithm that works by dividing the input list into two parts: the sorted part and the unsorted part.

The algorithm repeatedly finds the minimum (or maximum, depending on the sorting order) element from the unsorted part and swaps it with the first element of the unsorted part. This process is repeated until the entire list becomes sorted.

Step by Step procedure

1. Initialization

1. The algorithm starts with the entire list considered as unsorted.

2. Iteration

1. In each iteration, the algorithm scans the unsorted part of the list to find the minimum (or maximum) element.
2. It keeps track of the index of the minimum (or maximum) element found during the scan.

3. Swap

1. Once the minimum (or maximum) element is found, the algorithm swaps it with the first element of the unsorted part. This effectively adds the smallest (or largest) element to the sorted part of the list.

4. Incrementing the Sorted Part

1. The algorithm now considers the first element of the unsorted part as part of the sorted section. The sorted section grows by one element, and the unsorted section shrinks by one element.

5. Repeat

1. Steps 2 to 4 are repeated for the remaining unsorted part of the list until the entire list becomes sorted.

6. Termination

1. The algorithm terminates when the entire list is sorted, and the sorted part covers the entire list.

Invariants

In computer science and algorithms, invariants are properties or conditions that remain true during the execution of an algorithm or a portion of code. In the context of Selection Sort, there are a couple of invariants that hold true throughout the sorting process.

Let us see them to better understand the selection sort algorithm.

Invariant 1: Partial Sorting

• Throughout the execution of Selection Sort, the elements before the current position in the array are in their correct sorted positions.
• In other words, after i-th iteration of the algorithm, the first i elements (where i is the current iteration index) are sorted and in their final positions.
• No entry to the right of the current iteration index is smaller (or greater) than any entry to the left of the current iteration index depending on whether we are performing an ascending (or descending) sort.

Invariant 2: Unsorted Part Min/Max

• In each iteration of Selection Sort, the minimum (or maximum, depending on the sorting order) element of the remaining unsorted part is selected and placed at the beginning of the unsorted part.
• This ensures that the selected element is in the correct relative order within the sorted part, and the unsorted part is reduced by one element.

Invariant 3: Sorted Part Growing

• As Selection Sort progresses through iterations, the sorted part of the array grows by one element in each iteration.
• The newly added element comes from the unsorted part and is the smallest (or largest) element remaining.

These invariants help us understand and verify the correctness of the Selection Sort algorithm. They provide a way to reason about the behavior of the algorithm and ensure that it functions as intended. The invariants also help in identifying possible errors or bugs that might occur during implementation.

Pseudocode supporting invariants.

SelectionSort(A):
    n = length of array A
    
    for i from 0 to n - 1:
        min_index = i  // Assume the first element is the minimum
        
        // Find the index of the minimum element in the unsorted part
        for j from i + 1 to n - 1:
            if A[j] < A[min_index]:
                min_index = j
        
        // Swap the minimum element with the first element of the unsorted part
        swap A[i] with A[min_index]
    
    // Array is now sorted
    
    return A

In this pseudocode, the Selection Sort function takes an array A as input and sorts it using the Selection Sort algorithm. It supports the invariants as follows:

Invariant 1 (Partial Sorting)

• The outer loop runs from index 0 to n - 1. After each iteration (for each value of i), the first i elements are in their correct sorted positions.

Invariant 2 (Unsorted Part Min)

• The inner loop (second loop) scans the unsorted part of the array from index i + 1 to n - 1. It finds the minimum element in the unsorted part and updates min_index accordingly.

Invariant 3 (Sorted Part Growing)

• The swap operation places the minimum element found in the unsorted part at index i, effectively growing the sorted part by one element in each iteration.

Diagram 1

Python Code

def selection_sort(lst):

    # outer loop - go from first to penultimate element
    l = len(lst)
    for i in range(l-1):
        # Set current element as the minimum element and store its index
        min_index = i

        # Find the index of the minimum element in the unsorted part
        for j in range(i+1, l):
            if (lst[j] < lst[min_index]):
                min_index = j

        # Swap the minimum element with the first element of the unsorted part
        lst[min_index], lst[i] = lst[i], lst[min_index]

    return lst


# Example usage
input_array = [64, 25, 12, 22, 11]
sorted_array = selection_sort(input_array)

print("Input array:", input_array)
print("Sorted array:", sorted_array)

Example

input array [64, 25, 12, 22, 11]

Initial Array: [64, 25, 12, 22, 11]

Step 1: i = 0 (Minimum: 11)

• Find the minimum element in the entire array and swap it with the first element.
• Repeat the above step for every iteration.

[11, 25, 12, 22, 64]

Step 2: i = 1 (Minimum: 12)

[11, 12, 25, 22, 64]

Step 3: i = 2 (Minimum: 22)

[11, 12, 22, 25, 64]

Step 4: i = 3 (Minimum: 25)

[11, 12, 22, 25, 64]

Step 5: i = 4 (Minimum: 64)

• The array is now fully sorted. No swaps are needed.

[11, 12, 22, 25, 64]

The Selection Sort algorithm has successfully sorted the input array [64, 25, 12, 22, 11] in ascending order, and the final sorted array is [11, 12, 22, 25, 64].

Complexity Analysis

Let’s analyze the time complexity, space complexity, and stability of the Selection Sort algorithm.

Time Complexity

Selection Sort consists of two nested loops:

• The outer loop runs n times (where n is the number of elements in the array).
• The inner loop, within each iteration of the outer loop, runs from i + 1 to n - 1 times (approximately n / 2 on average).
• The number of comparisons in Selection Sort is approximately (n - 1) + (n - 2) + ... + 1, which is the sum of the first n - 1 natural numbers. This is an arithmetic series with a sum of (n - 1) * n / 2.
• The number of swaps in Selection Sort is at most n - 1 swaps.

Overall, the time complexity of Selection Sort is O(n²), where n is the number of elements in the array.

Space Complexity

• Selection Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory proportional to the input size. It only needs a constant amount of extra space for variables (like loop indices).

Therefore, the space complexity of Selection Sort is O(1), indicating constant space usage.

Stability

• Selection Sort is not stable by default. Stable sorting algorithms maintain the relative order of equal elements in the sorted output. In Selection Sort, the swapping step might change the relative order of equal elements.
• To make Selection Sort stable, we need to modify the swapping step so that it only occurs when the element to be swapped is strictly less than the current element. This ensures that the relative order of equal elements is maintained. Here’s how you can implement a stable version of Selection Sort in Python.

def stable_selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_index = i
        
        # Find the index of the minimum element in the unsorted part
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Swap elements while maintaining stability
        while min_index > i and arr[min_index] < arr[min_index - 1]:
            arr[min_index], arr[min_index - 1] = arr[min_index - 1], arr[min_index]
            min_index -= 1
    
    return arr

# Example usage
input_array = [4, 2, 2, 8, 3, 3, 1]
sorted_array = stable_selection_sort(input_array)

print("Input array:", input_array)
print("Sorted array:", sorted_array)

Adaptive

• Selection Sort is not an adaptive algorithm. An adaptive sorting algorithm is one that takes advantage of already sorted or partially sorted data to reduce the number of comparisons or swaps.
• Selection Sort always performs the same number of comparisons and swaps regardless of the input order.

Conclusion

Overall, while Selection Sort is easy to understand and implement, its time complexity of O(n²) makes it inefficient for large datasets. It is primarily used for educational purposes or in situations where the number of swaps is a concern due to high write costs (e.g., in flash memory). In most practical scenarios, more efficient sorting algorithms like QuickSort or MergeSort are preferred.