Selection Sort is an intuitive, in-place comparison sorting algorithm. It works by dividing the input list into two parts: a sorted sublist which is built up from left to right, and a sublist of the remaining unsorted items. Its method is simple and methodical: repeatedly find the minimum element from the unsorted part and move it to the end of the sorted part.
Quick Context: The Sorting Process
The algorithm proceeds as follows, iterating through the entire array:
- Outer Loop: The main loop iterates from the first element to the second-to-last element. This loop's counter (let's call it `i`) marks the boundary between the sorted part (elements before `i`) and the unsorted part (elements from `i` onwards).
- Inner Loop (Find Minimum): For each position `i`, a second loop scans the rest of the unsorted part of the array (from `i+1` to the end) to find the index of the smallest element.
- Swap: After the inner loop finds the minimum element in the unsorted portion, it is swapped with the element at the current position `i`.
After the first pass, the smallest element in the entire array is guaranteed to be in the first position. After the second pass, the second-smallest is in the second position, and so on. The visualization clearly shows this: the green bar is the current position `i`, the orange bar is the minimum element found so far, and the light green area represents the growing sorted portion of the array.
Core Idea: Select and Place
The name "Selection Sort" comes directly from its core operation: in each pass, it selects the minimum remaining element and places it in its correct sorted position. Unlike Bubble Sort, which makes many swaps in a single pass, Selection Sort makes only one swap per pass. This minimizes the number of writes to memory, which can be an advantage in specific scenarios (like writing to flash memory where writes are expensive).
Guided Experiments
Use the interactive controls to build a solid mental model of Selection Sort.
-
The First Pass:
Randomize the array and click "Next Step" repeatedly. In the first pass, the `i` pointer stays at index 0. Watch the `j` pointer scan the entire array. The "min" marker (orange bar) will update every time a new, smaller element is found. At the end of the pass, a single swap places the absolute minimum element at the start.
-
The Sorted Partition:
As you complete each pass, notice how the light green "sorted" area grows from the left. The algorithm never has to look at this part of the array again, effectively reducing the problem size by one element in each pass.
-
Best vs. Worst Case:
Randomize the array until you get one that is already sorted. Step through the algorithm. Notice that it still performs the same number of comparisons, even though no swaps are needed. Now, try it on a reverse-sorted array. The number of comparisons remains the same, but a swap occurs in every pass. This demonstrates why the algorithm's time complexity is the same regardless of the input data.
Performance and Complexity
Selection Sort is known for its simplicity, but not its speed, especially on large lists.
- Time Complexity: O(n²) - The algorithm has two nested loops. The outer loop runs `n-1` times and the inner loop runs `n-1`, `n-2`, ..., `1` times. This results in a quadratic time complexity in all cases (best, average, and worst), because it must always scan the entire remaining array to find the minimum element.
- Space Complexity: O(1) - It is an in-place sorting algorithm. It only requires a constant amount of extra memory for storing a few variables (like the loop counters and the index of the minimum element), regardless of the size of the input array.
Key Takeaways
- Simple to Understand: Its straightforward logic makes it easy to grasp and implement.
- Memory Efficient: The O(1) space complexity is a significant advantage.
- Inefficient for Large Lists: The O(n²) time complexity makes it impractical for sorting large datasets compared to algorithms like Merge Sort or Quick Sort.
- Minimal Swaps: It performs at most `n-1` swaps, which can be useful if write operations are costly.