We call a sorting algorithm stable if it assures that for any A[i] = A[j] and i < j, after the sort procedure, maintains that the new coressponding positions i' < j'.
Stable sort includes: bubble sort, insertion sort, merge sort
Nonstable sort includes: heap sort
Notice that quick sort is stable or not is dependent of the implementation.
Any sort algorithm can be changed into a stable one by extending the key with a original order number. E.g. <1, 9, 8, 1> can be extended as <1.1, 9.2, 8.3, 1.4>.
A stable version will cost no less time and memory than a nonstable version sort. Abstractly, stable is a constraint, any constraint for the result of the output form of an algorithm will take some cost. The reason is that a constraint on the output will take some unnessesary cost than the non-stable one. stable is a special case of a nonstable one.
No comments:
Post a Comment