Selection Sort is generally not stable. Stability in sorting algorithms refers to the preservation of the relative order of equal elements in the sorted output as they appeared in the original input. In the case of Selection Sort, the algorithm does not guarantee the stability of the sorting.
The instability arises when there are equal elements in the unsorted part of the array, and the algorithm selects one of them to swap with the first unsorted element. Since the selection is based on finding the minimum (or maximum) element, and there's no consideration for the original order of equal elements, the relative order of equal elements might not be preserved during the swap.
To illustrate, consider the following example:
Initial array: [4a, 3, 1, 4b, 2]
Here, 4a and 4b are equal elements. In the first pass, the algorithm might select 1 as the minimum and swap it with the first unsorted element (4a):
- After the first pass: [1, 3, 4a, 4b, 2]
In this case, the relative order of 4a and 4b is changed after the sorting process, indicating that Selection Sort is not stable.
Stability is an important property in certain sorting scenarios, and if maintaining the original order of equal elements is crucial, other stable sorting algorithms, such as merge sort or insertion sort, are preferred over Selection Sort.
