Selection Sort
Performance
Press the 'Play Animation' button.
Sorting Statistics
Swaps:
0
Comparisons:
0
Array Accesses:
0
Delay: 45 ms | Size: 20
⚠️ Note: this animated visualization is a work-in-progress. If you are encountering errors or want to replay the animation, please refresh the page.
If you would like to report a bug or suggest an improvement, please create an issue on GitHub.
Understanding Selection Sort
Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning of the array. The algorithm maintains two subarrays in a given array:
- The subarray which is already sorted.
- Remaining subarray which is unsorted.
During the sorting process there are the following operations:
- Find the minimum element in the unsorted subarray.
- Swap the found minimum element with the first element of the unsorted subarray.
Complexity Analysis
Selection Sort has the following complexities:
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Best Case | Ω(n²) | Ω(1) |
| Average Case | Θ(n²) | Θ(1) |
| Worst Case | O(n²) | O(1) |
It has a quadratic time complexity, meaning that the number of steps required to sort the array grows quadratically as the size of the array increases. This is because the algorithm has to perform a linear scan of the array for each element in the array. It also has a linear space complexity.
Code Implementation
Selection Sort can be implemented in a variety of languages. Below are some examples of implementations in Python, C++, Go, and Java.
Note: these implementations are for educational purposes only, such as preparing for a technical interview or for learning about sorting algorithms. For production code, please use the built-in sorting functions in your programming language's standard library.
When should Selection Sort be used?
Selection Sort is a simple sorting algorithm that works well for small data sets or when you are not concerned about performance. It is also a good choice when memory space is limited, as it is an in-place sorting algorithm.
In the real world, Selection Sort is rarely used because it is very inefficient for large data sets. It is also not a stable sorting algorithm, meaning that the relative order of equal sort items is not preserved.