What is Selection Sort?¶

Selection sort is a simple and intuitive sorting algorithm. Its core idea is to find the smallest (or largest) element from the unsorted elements each time and place it at the end of the sorted portion, until all elements are sorted. Imagine organizing a shuffled deck of playing cards: you pick the smallest card one by one from the deck and place it on the left side of the table in order until all cards are sorted.

Steps of Selection Sort¶

1. Initialization: Assume the first element of the array is the current smallest element (i.e., position 0 is the end of the sorted portion).
2. Traverse to Find the Minimum: Starting from the next element of the current unsorted portion, traverse the entire unsorted region to find an element smaller than the current minimum and update the position of the minimum.
3. Swap Positions: Swap the found minimum element with the first element of the current unsorted portion. At this point, this element is “fixed” at the end of the sorted portion.
4. Repeat: Repeat the above steps until the unsorted portion is empty (i.e., all elements are sorted).

Python Code Implementation¶

Here is the Python implementation of selection sort with detailed comments for clarity:

def selection_sort(arr):
    # Get the length of the array
    n = len(arr)
    # Outer loop: control the range of elements to be sorted (from 0 to n-2, since the last element needs no sorting)
    for i in range(n - 1):
        # Assume the element at position i is the current minimum
        min_index = i
        # Inner loop: find a smaller element from i+1 to n-1
        for j in range(i + 1, n):
            # If a smaller element is found, update the position of the minimum
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the element at position i with the found minimum element
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Test code
if __name__ == "__main__":
    # Unsorted array
    unsorted = [64, 25, 12, 22, 11]
    print("Before sorting:", unsorted)
    # Call the selection sort function
    sorted_arr = selection_sort(unsorted)
    print("After sorting:", sorted_arr)

Code Explanation¶

• Outer Loop: The variable i ranges from 0 to n-2 (using range(n-1)), representing the end position of the sorted portion. After each loop iteration, arr[i] is fixed as the i-th element of the sorted portion (the minimum).
• Inner Loop: The variable j ranges from i+1 to n-1, traversing all elements in the unsorted portion to find the position min_index of the smallest element.
• Swap Operation: After finding the minimum, the elements at positions i and min_index are swapped using arr[i], arr[min_index] = arr[min_index], arr[i], ensuring the minimum is “placed” at the end of the sorted portion.

Running Result¶

When running the test code, the output is as follows:

Before sorting: [64, 25, 12, 22, 11]
After sorting: [11, 12, 22, 25, 64]

Complexity Analysis¶

• Time Complexity: Regardless of the input data, selection sort requires two nested loops (outer loop runs n times, inner loop runs n times). Thus, the time complexity is O(n²) (where n is the array length).
• Space Complexity: Selection sort is an in-place sorting algorithm. It does not require additional array space, so the space complexity is O(1).

Characteristics of Selection Sort¶

• Simple and Intuitive: Clear logic, easy to understand and implement, suitable for beginners to learn the basic idea of sorting algorithms.
• Unstable Sort: If there are duplicate elements, the relative order may change (e.g., the array [2, 2, 1] may become [1, 2, 2], but the original order of the two 2s may be swapped).
• In-place Sort: No additional space is needed; sorting is completed by swapping elements alone.

Although selection sort has a high time complexity, it still has practical value for sorting small-scale data. It is particularly useful for understanding the basic principles of sorting algorithms. With the above steps and code, you have mastered how to implement selection sort in Python!