Stable한 정렬이란??

stable sort는 정렬 알고리즘 중 하나로, 정렬 과정에서 동일한 값에 대해 입력순서와 같은 상대적인 순서를 유지하는 정렬을 말한다.

예를 들어

같은 값을 가진 두 요소 A,B가 있을 때, A가 B보다 먼저 입력되었다면 정렬 결과에서도 A가 B보다 먼저 나오는 것을 말한다.

좀 더 자세한 예를 들어서

학생의 이름과 점수가 입력된 데이터에서 이름으로 먼정 정렬을 하고, 그 다음에 점수로 정렬하는 경우를 생각해보자, 같은 이름과 점수를 가진 학생들은 이름으로 정렬된 상태에서도 점수순으로 정렬된 상태에서도 서로 같은 상대적인 위치를 유지해야 한다. 이러한 경우에는 stable sort를 사용해야 한다.

stable sort의 대표적인 예는 Merge Sort, Insertion Sort, Bubble sort 등이 안정 정렬 알고리즘이다.

더 나아가서 Unstable sort에 대해서도 알아보자

Unstable sort는 정렬 과정에서 같은 값에 대해 상대적인 순서가 유지되지 않을 수 있는 정렬을 말한다. 즉, 같은 값을 가진 두 요소 A,B가 있을 때, A가 B보다 먼저 입력되었다고 해서 정렬 결과에서 A가 항상 B보다 앞에 나오는 것을 보장하지 않는다.

한 줄 요약 : 정렬 결과가 상대적인 순수에 따라 정확히 유지되어야 하는 경우에는 사용하지 않아야 합니다.