[Algorithm] 안정 정렬과 불안정 정렬

 

 

4개의 메뉴를 담은 ArrayList 를 가격을 기준으로 정렬을 했다.

그런데 아메리카노와 카페모카의 가격이 같다. 그 경우 어떻게 정렬이 이루어질까?

 

어떤 정렬 알고리즘을 사용하느냐에 따라 결과값이 달라지게 된다.

 

안정 정렬(Stable sort)

안정 정렬은 1차적인 정렬이 이루어진 상태에서, 중복된 값이 있을 경우, 입력순서와 동일하게 정렬이 이루어지는 정렬 알고리즘의 특성 중 하나이다. 

 

이러한 안정 정렬의 특성을 지닌 정렬 알고리즘에는 버블 정렬, 삽입정렬, 병합 정렬이 있다.

 

불안정 정렬(Unstable sort)

불안정 정렬은 안정 정렬의 반댓말로, 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘을 의미한다.

 

선택 정렬, 퀵 정렬, 계수 정렬 등이 이에 해당한다.