[CS] Stable & Unstable Sort

정렬의 종류 : stable & unstable

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되는 경우를 stable sort라고 한다.

예를 들어

age	name
3	A
3	B
3	C
1	D
2	F

의 경우에, age 순으로 정렬을 했을 때

age	name
1	D
2	F
3	A
3	B
3	C

위와 같이 정렬 전에 age가 3인 경우 A, B, C의 순서가 정렬 후에도 유지되는 경우를 stable한 sort라고 한다. 대표적으로 merge sort가 있다.

반대로 unstable sort는 A, B, C의 순서가 보장되지 않는 정렬을 말한다. 대표적으로 Quick, heap sort 등이 있다.