What is the Algorithm of Selection Sort?

Selection Sort is a straightforward, in-place comparison sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

How Selection Sort Works: The Step-by-Step Algorithm

The core idea of Selection Sort is to divide the input list into two parts: a sorted sublist and an unsorted sublist. Initially, the sorted sublist is empty, and the unsorted sublist contains all elements. The algorithm then iteratively finds the smallest (or largest, depending on the sort order) element from the unsorted sublist and moves it to the sorted sublist.

Here's a detailed breakdown of the algorithm:

1. Initialize: Start with the entire list considered as the unsorted sublist. The first element acts as the current minimum's assumed position.
2. Iterate Through the List:
   • For each pass, starting from the first element up to the second-to-last element of the array:
     • Assume the current element (at index i) is the minimum.
     • Find the Minimum: Traverse the rest of the unsorted sublist (from i+1 to the end of the array) to find the actual minimum element.
     • Track Minimum's Index: Keep track of the index of this newly found minimum element.
     • During this search, the algorithm performs n-1, n-2, ..., 1 comparisons in each respective iteration.
3. Swap Elements:
   • If the minimum element found in step 2 is not at the assumed minimum's position (index i), swap it with the element at index i.
   • Each element is swapped at most once throughout the entire sorting process. This leads to a maximum of O(n) swaps.
4. Repeat: Increment the starting point of the unsorted sublist (effectively increasing the size of the sorted sublist by one) and repeat steps 2 and 3 until the entire list is sorted.

Key Characteristics and Properties

Selection Sort possesses several distinct characteristics:

• In-Place Algorithm: It sorts the array by modifying the original list directly without requiring additional memory proportional to the input size.
• Space Complexity: It uses constant extra space, making it an O(1) space complexity algorithm.
• Time Complexity:
  • Best Case: O(n²)
  • Average Case: O(n²)
  • Worst Case: O(n²)
    This quadratic time complexity arises because it always performs (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons, regardless of the initial order of elements.
• Swaps: It makes at most O(n) swaps, which can be beneficial in scenarios where writing to memory (swaps) is significantly more expensive than reading (comparisons).
• Stability: Selection Sort is not stable. This means that the relative order of equal elements may be reordered during the sorting process. For example, if you have two identical numbers, their original positions relative to each other might change after sorting.
• Adaptivity: It is not an adaptive algorithm, meaning its performance does not improve for partially sorted arrays.

Example Walkthrough

Let's sort the array [64, 25, 12, 22, 11] using Selection Sort.

Original Array: [64, 25, 12, 22, 11]

Pass 1 (i = 0):

• Assume 64 (at index 0) is the minimum.
• Scan the rest of the array [25, 12, 22, 11].
• The minimum element is 11 at index 4.
• Swap 64 and 11.
• Array after Pass 1: [11, 25, 12, 22, 64] (Sorted part: [11])

Pass 2 (i = 1):

• Assume 25 (at index 1) is the minimum in the unsorted part [25, 12, 22, 64].
• Scan [12, 22, 64].
• The minimum element is 12 at index 2.
• Swap 25 and 12.
• Array after Pass 2: [11, 12, 25, 22, 64] (Sorted part: [11, 12])

Pass 3 (i = 2):

• Assume 25 (at index 2) is the minimum in the unsorted part [25, 22, 64].
• Scan [22, 64].
• The minimum element is 22 at index 3.
• Swap 25 and 22.
• Array after Pass 3: [11, 12, 22, 25, 64] (Sorted part: [11, 12, 22])

Pass 4 (i = 3):

• Assume 25 (at index 3) is the minimum in the unsorted part [25, 64].
• Scan [64].
• The minimum element is 25 at index 3 (already in place). No swap needed.
• Array after Pass 4: [11, 12, 22, 25, 64] (Sorted part: [11, 12, 22, 25])

The array is now fully sorted.

When to Use Selection Sort

Despite its O(n²) time complexity, which makes it inefficient for large datasets compared to algorithms like Merge Sort or Quick Sort, Selection Sort can be useful in specific scenarios:

• Small Lists: For very small arrays, the constant factor overhead might be lower than more complex algorithms.
• Memory-Constrained Environments: Its O(1) space complexity is advantageous when memory is extremely limited.
• Minimizing Swaps: If the cost of swapping elements is very high (e.g., large data structures being moved around), Selection Sort's property of performing only O(n) swaps can be a significant advantage.

Summary Table

Feature	Description
Algorithm Type	Comparison Sort
Stability	Not Stable
In-Place	Yes
Time Complexity	O(n²) (Best, Average, Worst)
Space Complexity	O(1)
Swaps	O(n)
Comparisons	O(n²)
Best Use Case	Small datasets, memory-constrained systems, or when minimizing data movement (swaps) is critical.

For a more comprehensive understanding of various sorting algorithms, you can explore resources like Wikipedia's page on Sorting Algorithms.