stable sort what? why? which?

1. what stable sort ?

[출처 : https://www.geeksforgeeks.org/stability-in-sorting-algorithms/ ]

stable sort란 무엇일까요? 

아래 공들은 정렬이 된 상태입니다. 정렬되기 전과 비교했을 때 특징이 있습니다.

그것은 공의 숫자는 정렬되었지만, 같은 숫자를 가진 공 사이에 색깔은 들어온 순서를 유지한다는 것입니다.

이것이 바로 stable sort 의 개념! 입니다. 

(unstable sort 는? 그 반대겠죠. 그냥 막 섞입니다.)

2. why stable sort ?

그럼 이 stable sort가 왜 중요할까요?

예 ) 데이터가 들어온 순서는 유지하면서, 특정 key 값을 기준으로 sorting하고 싶을 때 그냥 아무생각 없이 sort 함수 돌리면

안됩니다. 지금 적용하려는 algorithm이 stable한지 확인하고 적용해야 합니다. 

그리고 그냥 대충 생각해도 내가 원하는 기준이 아닌 다른 기준은 건들이지 않는게 좋잖아요?ㅎㅎㅎ

stable sort를 사용합시다 ~

3. which stable sort algorithm ?

아 그럼 stable sort가 뭔지도 알았고, 왜 사용하는지도 알았는데 어떤 algorithm이 stable한데? 라는 의문이 생깁니다.

1. stable sort : merge sort / bubble sort / insertion sort

2. unstable sort : quick sort / heap sort 

대표적으로는 위와 같고요. 그런데 중요한 건 unstable이라고 해서 무조건이냐? 하면 그렇지 않습니다.

unstable sort도 내부적으로 같은 key 값을 갖는 tuple에 대해서는 상대적 위치를 지킬 수 있게끔 로직을 작성한다면

충분히 stable sort로 사용할 수 있습니다.