Python Selection Sort

Python Selection Sort

Selection Sort is another simple, in-place sorting algorithm. The main idea is to divide the list into two parts: the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted part and swapping it with the leftmost element of the unsorted part. This moves the boundary between the sorted and unsorted parts one element to the right.

How Selection Sort Works

1. Assume the first element is the minimum.
2. Iterate through the rest of the unsorted part of the list.
3. If you find an element smaller than the current minimum, update the minimum.
4. After checking all elements in the unsorted part, you will have found the absolute minimum element.
5. Swap this minimum element with the first element of the unsorted part.
6. The first element is now considered sorted. Move the boundary one to the right and repeat the process for the new unsorted part.
7. Continue until the entire list is sorted.

Implementing Selection Sort in Python

Here is a function that implements the selection sort algorithm.

def selection_sort(data):
    n = len(data)
    // Traverse through all array elements
    for i in range(n):
        // Find the minimum element in the remaining unsorted array
        min_idx = i
        for j in range(i+1, n):
            if data[j] < data[min_idx]:
                min_idx = j
        // Swap the found minimum element with the first element
        data[i], data[min_idx] = data[min_idx], data[i]

// --- Usage ---
my_list = [64, 25, 12, 22, 11]
selection_sort(my_list)
print("Sorted list is:", my_list)

Time Complexity

Selection sort's performance is not dependent on the initial order of the data.

• Best Case: O(n²)
• Worst Case: O(n²)
• Average Case: O(n²)

The reason it's always O(n²) is that it must iterate through the remaining items to find the minimum in every pass, regardless of whether the list is already sorted or not. It performs fewer swaps than Bubble Sort but has the same time complexity.