Understanding Selection Sort in Python

[Rajeev Bagra]

Selection Sort is one of the simplest sorting algorithms. The idea is straightforward: repeatedly find the smallest element from the unsorted portion of a list and move it to its correct position.

Python Implementation

def SelectionSort(L):
    for i in range(len(L)):
        minindex = i
        smallest = L[i]

        for j in range(i + 1, len(L)):
            if L[j] < smallest:
                minindex = j
                smallest = L[j]

        L[i], L[minindex] = L[minindex], L[i]

    return L

How the Algorithm Works

The outer loop selects the position where the next smallest element should be placed. Initially, the algorithm assumes that the current element is the smallest.

minindex = i
smallest = L[i]

The inner loop then scans the remaining unsorted elements to find a smaller value.

for j in range(i + 1, len(L)):
    if L[j] < smallest:
        minindex = j
        smallest = L[j]

If a smaller element is found, both its value and index are recorded.

Swapping Elements

After the smallest element in the unsorted portion has been identified, it is swapped into its correct position.

L[i], L[minindex] = L[minindex], L[i]

This places the smallest remaining element at index i.

Example

Suppose the list is:

[7, 3, 8, 1]

During the first pass, the algorithm finds that 1 is the smallest element and swaps it with 7.

[1, 3, 8, 7]

On subsequent passes, the algorithm continues sorting the remaining unsorted elements until the entire list is ordered.

[1, 3, 7, 8]

Time Complexity

Selection Sort performs approximately:

[latex]n(n-1)/2[/latex]

comparisons, which gives it a time complexity of:

[latex]O(n^2)[/latex]

This means Selection Sort is suitable for learning and small datasets, but more efficient algorithms such as Merge Sort or Quick Sort are preferred for large datasets.

Key Takeaway

Selection Sort works by maintaining a sorted and an unsorted portion of the list. In each pass, it selects the smallest element from the unsorted portion and places it into its correct position, gradually building the sorted list from left to right.

[Author]

Posts