Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts: a sorted part and an unsorted part. In each iteration, the smallest (or largest) element from the unsorted part is selected and swapped with the first element of the unsorted part.
How Selection Sort Works:
- Start from the first element of the array.
- Find the minimum element in the unsorted part of the array.
- Swap the minimum element with the first element of the unsorted part.
- Move the boundary of the sorted and unsorted parts by one, and repeat until sorted.
Complexity Analysis:
- Time Complexity: O(n²) for best, average, and worst cases.
- Space Complexity: O(1) (in-place sorting).
Characteristics:
- Selection Sort is not stable (relative order of equal elements may change).
- It is an in-place sorting algorithm.
- Simple to implement but inefficient for large datasets.
- The graph describing the Selection Sort time complexity looks like this:
