Selection Sort Visualizer
What is Selection Sort
Selection Sort is an in-place comparison sorting algorithm that divides the input list into two parts: a sorted sublist which is built up from left to right, and a remaining unsorted sublist. It repeatedly selects the smallest (or largest) element from the unsorted portion and moves it to the sorted portion.
How Does It Work
- First Pass:
- Find the minimum in [64, 25, 12, 22, 11] → 11 at index 4
- Swap with first element → [11, 25, 12, 22, 64]
- Second Pass:
- Find minimum in [25, 12, 22, 64] → 12 at index 2
- Swap with first element → [11, 12, 25, 22, 64]
- Third Pass:
- Find minimum in [25, 22, 64] → 22 at index 2
- Swap with first element → [11, 12, 22, 25, 64]
- Fourth Pass:
- Find minimum in [25, 64] → 25 at index 0
- No swap needed → [11, 12, 22, 25, 64]
- Result: [11, 12, 22, 25, 64]
Algorithm Steps
- Set the first element as minimum
- Compare minimum with the second element:
- If second element is smaller, set it as new minimum
- Continue until last element is reached
- Swap minimum with first element
- Repeat for remaining unsorted portion
Time Complexity
- Best Case: O(n²) (still makes n(n-1)/2 comparisons)
- Average Case: O(n²)
- Worst Case: O(n²)
The quadratic time complexity occurs because it performs O(n) comparisons for each of the O(n) elements.
Space Complexity
Advantages
- Simple to understand and implement
- Performs well on small lists
- Minimal memory usage (in-place sorting)
- Only O(n) swaps required (better than Bubble Sort)
Disadvantages
- Poor performance on large lists (quadratic time complexity)
- Not stable (may change relative order of equal elements)
- Less efficient than Insertion Sort for nearly sorted data
- Always performs O(n²) comparisons regardless of input
Selection Sort is primarily used for educational purposes to introduce sorting concepts. In practice, it's outperformed by more advanced algorithms like QuickSort and MergeSort, but can be useful when memory writes are expensive (since it makes only O(n) swaps).
Visualize Selection Sort as it repeatedly selects the smallest element and swaps it to its correct position in the array.