Selection Sort

Selection Sort Algorithm

In the previous tutorial, we learned about Bubble Sort. Now, let's look at another classic algorithm: Selection Sort.

While Bubble Sort swaps adjacent elements constantly, Selection Sort minimizes swaps by searching for the absolute smallest element first.

1. How Does Selection Sort Work?

Selection Sort divides the array into two parts:

1. The sorted part at the front.
2. The unsorted part at the back.

Initially, the sorted part is empty, and the unsorted part is the entire array.

The algorithm works like this:

• Look through the entire unsorted part to find the smallest number.
• Swap that smallest number with the first number of the unsorted part.
• Move the boundary one step to the right.
• Repeat until the whole array is sorted!

Selection Sort: Scan for the smallest item, then swap it into its correct place.

2. A Step-by-Step Example

Let's sort an array of numbers from lowest to highest: [8, 5, 2, 9, 4]

Pass 1:

• Search the whole array: [8, 5, 2, 9, 4].
• The minimum value is 2.
• Swap 2 with the first element 8.
• Array is now: [2, 5, 8, 9, 4]. The number 2 is sorted.

Pass 2:

• Search the remaining unsorted array: [5, 8, 9, 4].
• The minimum value is 4.
• Swap 4 with the first unsorted element 5.
• Array is now: [2, 4, 8, 9, 5]. The numbers 2, 4 are sorted.

Pass 3:

• Search the remaining unsorted array: [8, 9, 5].
• The minimum value is 5.
• Swap 5 with 8.
• Array is now: [2, 4, 5, 9, 8].

Pass 4:

• Search the remaining unsorted array: [9, 8].
• The minimum value is 8.
• Swap 8 with 9.
• Array is now completely sorted: [2, 4, 5, 8, 9].

3. Selection Sort Code Example

Let's write the Selection Sort algorithm in Python.

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

numbers = [8, 5, 2, 9, 4]
print("Original:", numbers)
print("Sorted:", selection_sort(numbers))

4. Time Complexity

• Time Complexity: O(n²).
• Space Complexity: O(1). It sorts the array in-place, meaning it doesn't require any extra memory.

Time Complexity Calculation

Why is it exactly O(n²)? Let's break down the math:

• For an array of size n, the first pass checks n-1 elements to find the minimum.
• The second pass checks n-2 elements.
• The third pass checks n-3 elements, and so on, down to 1 operation.

If we add all those comparisons together: (n-1) + (n-2) + ... + 1. In mathematics, the sum of the first n-1 integers equals n * (n - 1) / 2.

When we use Big O Notation, we ignore constants (like / 2) and smaller terms (like - n), leaving us with the dominant term: O(n²). Because of this, Selection Sort always scans the entire unsorted portion of the array, even if the array is already perfectly sorted!

The number of comparisons decreases linearly, forming a triangle. The total area (total operations) is proportional to n² / 2.

Although it has the same O(n²) time complexity as Bubble Sort, Selection Sort is generally a little bit faster because it performs far fewer memory swaps!