정렬(sorting)이란 특정 물건이나 데이터를 조건에 따라오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 말한다.
예를 들자면 책을 정렬할 때 제목순, 발간 연도 순 등을 예시로 들 수 있다.
정렬은 조건, 방법등에 따라서 안정 정렬과 불안정 정렬, 내부 정렬과 외부 정렬 등으로 나뉘게 된다.
정렬의 안정적 특성
정렬의 안정적 특성은 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐이다.
정렬을 할 때 특정 기준을 따라서 정렬을 하게 된다.
정렬을 할 때 꼭 순서를 보장하는 방식이 있고, 그렇지 않은 방식이 존재한다.
데이터가 key, value형태의 데이터라면 그 차이가 더욱 명확하게 보일 것이다.
안정 정렬(Stable Sort)
안정 정렬은 정렬 후에도 그 순서가 유지된다.
위 사진을 보면 윗줄에는 정렬 전으로 7♠, 5♥, 2♥, 5♠ 순서로 나열되어 있다.
그리고 밑줄은 정렬된 결과로 2♥, 5♥, 5♠, 7♠ 순서로 나열되어 있다.
2♥와 7♠ 정렬로 인하여 맨 앞과 뒤로 배치되었지만, 윗 줄 순서인 5♥, 5♠는 밑줄에서도 5♥, 5♠ 순서를 유지하는 것을 확인할 수 있다.
이처럼 안정 정렬은 기존 순서를 유지하는 정렬이다.
불안정 정렬(Unstable Sort)
불안정 정렬은 정렬 후에 기존 순서가 유지된다는 보장을 할 수 없다.
윗 사진에서 윗줄은 똑같이 7♠, 5♥, 2♥, 5♠ 순서로 나열되어 있다.
그러나 밑줄은 2♥, 5♠, 5♥, 7♠ 순서로 나열되어 있다.
안정 정렬과는 달리 윗 줄 순서인 5♥, 5♠는 밑줄에서 5♠, 5♥ 순서로, 위치가 바뀐 것을 알 수 있다.
이처럼 불안정 정렬은 꼭 기존 순서가 유지되지 않을수도 있는 정렬이다.
Reference
