Selection Sort: Algorithm Explanation and Implementation

What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm that divides the input list into two parts:

• The sorted part at the beginning.
• The unsorted part occupying the rest of the list.

The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted part, swapping it with the first element of the unsorted portion, and progressively expands the sorted portion by one element.

Characteristics:

• In-Place: Requires no extra memory apart from the input array.
• Unstable: It may not preserve the relative order of equal elements.
• Inefficient for large datasets: Because of the quadratic time complexity, Selection Sort is inefficient for large datasets.

How Selection Sort Works:

1. Start with the first element and consider it the minimum.
2. Traverse the rest of the array to find the actual minimum element.
3. Swap the found minimum element with the first element.
4. Move to the next position and repeat the process for the rest of the array.

This process continues until the array is completely sorted.

Algorithm Steps:

1. Find the minimum in the unsorted array.
2. Swap it with the leftmost unsorted element.
3. Move the boundary between sorted and unsorted parts one element to the right.
4. Repeat until the whole array is sorted.

Flowchart for Selection Sort Algorithm Steps

Time Complexity:

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

Selection Sort always has a time complexity of O(n²) due to its two nested loops, where n is the number of elements in the list.

Auxiliary Space: O(1)
The good thing about selection sort is it never makes more than O(n) swaps and can be useful when the memory write is a costly operation.

Example of Selection Sort in Action:

Initial array:

[64, 25, 12, 22, 11]

• Step 1: Find the minimum element from index 0 to 4 → 11 (Swap 11 with 64):
  [11, 25, 12, 22, 64]

• Step 2: Find the minimum element from index 1 to 4 → 12 (Swap 12 with 25):
  [11, 12, 25, 22, 64]

• Step 3: Find the minimum element from index 2 to 4 → 22 (Swap 22 with 25):
  [11, 12, 22, 25, 64]

• Step 4: Find the minimum element from index 3 to 4 → 25 (No swap needed):
  [11, 12, 22, 25, 64]

Now, the array is sorted!