Menu
This might be trivial, but I don't understand why the default implementation of Selection Sort is not stable?
At each iteration you find the minimum element in the remaining array. When finding this minimum, you can choose the first minimum you find, and only update it when an element is actually smaller than it. So, the chosen element at each iteration is the first minimum - meaning, it's first on the previous sort order. So, to my understanding, the current sort will not destroy an order generated by a previous sort on equal elements.
What am I missing?
454
The primary disadvantage of the selection sort is its poor efficiency when dealing with a huge list of items. Similar to the bubble sort, the selection sort requires n-squared number of steps for sorting n elements.
The stability of a sorting algorithm is concerned with how the algorithm treats equal (or repeated) elements. Stable sorting algorithms preserve the relative order of equal elements, while unstable sorting algorithms don't.
The following are the disadvantages of the selection sort. It performs poorly when working on huge lists. The number of iterations made during the sorting is n-squared, where n is the total number of elements in the list. Other algorithms, such as quicksort, have better performance compared to the selection sort.
Heap sort is not stable because operations in the heap can change the relative order of equivalent keys. The binary heap can be represented using array-based methods to reduce space and memory usage. Heap sort is an in-place algorithm, where inputs are overwritten using no extra data structures at runtime.
A small example:
Let b = B in
< B > , < b > , < a > , < C > (with a < b < c)
After one cycle the sequence is sorted but the order of B and b has changed:
< a > , < b > , < B > , < c >
But you can however implement Selections Sort stable if you, instead of switching, insert the minimum value. But for that to be efficient you should have a data structure that supports insertion at a low cost or otherwise you end up with quadratic complexity.
179
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
