안정정렬 불안정정렬

같은 값에 대해 들어온 순서가 유지 되는가에 따라 나뉘어진다.

같은 값이라도 정렬 전 순서대로 정렬되는 것은 안정정렬

같은 값 끼리는 정렬 전 순서와 정렬 후 순서가 달라질 수 있는 것은 불안정정렬

 

1.안정정렬 (Stable Sorting)

동일한 값을 가진 요소들의 상대적인 순서가 정렬 전과 동일하게 유지된다.

버블정렬, 삽입정렬, 병합정렬이 이에 해당한다.

 

2.불안정정렬 (Unstable Sorting)

불안정정렬은 동일한 값들에 대해서는 정렬 후 순서가 변경 될 수 있다.

퀵정렬, 힙정렬, 선택정렬이 이에 해당한다.

 

그렇다면 불안정 정렬을 굳이 쓰는 이유가 무엇이냐?

일번적으로 불안정 정렬이 안정 정렬에 비해 속도가 빠르기 때문이다.

하지만 같은 값에 대한 상대적인 순서가 중요한 경우에는 사용할 수 없을 것이다.