Selection Sort Visualization
Selection Sort is another comparison-based algorithm that sorts an array by repeatedly finding the minimum element from the unsorted part and moving it to its correct position. It minimizes the number of swaps needed compared to Bubble Sort, which makes it useful when the cost of moving items is high, but finding the smallest item is easy.
Pseudocode
for i = 0 to (n - 1):
min = i
for j = i + 1 to (n - 1):
if arr[j] < arr[min]:
min = j
if min != i: swap(i, min)
Visualizer
Select number of elements:
How It Works
Selection Sort divides the array into two logical parts: a sorted region at the beginning and an unsorted region at the end. In each iteration, the algorithm scans the entire unsorted region to find the smallest element. Once found, that element is swapped with the first element of the unsorted region, effectively expanding the sorted region by one. This process repeats until the entire array is sorted. Unlike Bubble Sort, which may perform multiple swaps per pass, Selection Sort performs a single swap only after finding the final minimum for that pass.
When to Use
Selection Sort is best suited for small arrays or situations where memory writes are significantly more expensive than reads (such as writing to flash memory). Due to its quadratic time complexity, Selection Sort is impractical for large datasets. It is also unstable, meaning the relative order of equal elements may not be preserved. More advanced divide-and-conquer algorithms are generally the industry standard for efficiency.
Time & Space Complexity
Metric / Operation | Complexity | Description |
|---|---|---|
| Best Case | O(n²) | Even if the array is already sorted, Selection Sort still scans the entire unsorted portion in each pass to confirm the minimum. |
| Average Case | O(n²) | The number of comparisons is always n(n-1)/2 regardless of input order. |
| Worst Case | O(n²) | Same as average case — the algorithm always performs the same number of comparisons. |
| Space Complexity | O(1) | Selection Sort is an in-place algorithm requiring only a constant amount of extra memory for the swap variable. |
Common Interview Questions
Why is Selection Sort unstable in its standard array-based implementation?
Selection Sort finds the minimum element in the unsorted sublist and swaps it with the element at the beginning of the unsorted sublist. This long-distance swap can jump over identical keys, altering their original relative order.
// Example: [4a, 4b, 2] // Swap 4a with 2 -> Array becomes [2, 4b, 4a] (4a and 4b relative order broken)
How can Selection Sort be extended to perform double selection?
Double Selection Sort finds both the minimum and maximum elements in a single pass of the unsorted sublist, placing the minimum at the start and the maximum at the end. This reduces the required passes from n to n / 2, though overall complexity remains O(n²).
Why doesn't Selection Sort adapt to sorted data?
Selection Sort always takes O(n²) time regardless of whether the array is already sorted, reverse-sorted, or random. The algorithm must complete all comparisons in the unsorted scan to confirm it has found the true minimum value.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0