Definition
When sorting a list, the resulting values may be the same, but the difference in the internal sorting process creates a distinction between stable and unstable sorting methods.
Stable sorting preserves the original position of elements in the list while sorting. Unstable sorting does not preserve the original position of elements in the list while sorting.
Example
Consider the following list: [A, C, A, B, C, D]. When sorting this list in lexicographic order, it would result in [A, A, B, C, C, D]. However, it is possible to distinguish between the first occurrence of A and the second occurrence of A by assigning a unique index to each occurrence:
Given sort:
[A(1), C(1), A(2), B, C(2), D]
Stable sort:
[A(1), A(2), B, C(1), C(2), D]
Unstable sort:
[A(2), A(1), B, C(1), C(2), D]
댓글 없음:
댓글 쓰기