Selection Sort
Selection Sort is an in-place comparison sorting algorithm. It divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front of the list, and a sublist of the remaining unsorted items that occupy the rest of the list.
The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.
Complexity
| Best Time | Average Time | Worst Time | Space |
|---|---|---|---|
| O(N²) | O(N²) | O(N²) | O(1) |
How It Works (Step-by-Step)
- Assume the first unsorted element is the minimum.
- Iterate through the rest of the unsorted array to find if there is an element smaller than the current minimum.
- If a smaller element is found, designate it as the new minimum.
- Once the end of the array is reached, swap the minimum element found with the first unsorted element.
- The first unsorted element is now considered part of the sorted sublist. Repeat steps 1-4 until the array is fully sorted.