데이터를 정렬해야하는 경우는 매우 많고 정렬를 하는 방식도 매우 다양하다.
정렬을 할때는 어떻게 정렬을 해야할지 먼저 생각해야한다.
예를 들어 숫자를 정렬할때는 오름차순으로 할지, 내림차순으로 할지 정해야하고
알파벳을 정렬할 때는 대소문자를 구분할 것인지, 아닌지 정해야한다.
책꽂이에 꽂혀있는 책들을 다시 정렬해야한다고 경우가 생겼다고 가정해보자.
책들을 모두 바닥에 꺼내고 가장 먼저 꽂아놓을 책부터 순서대로 꽂아 놓는 방법이 있을것이다.
이런 경우 책을 모두 꺼내서 놓을 추가적인 공간이 필요하다.
하지만 책을 모두 꺼내는 대신 한 권만 꺼내서 손에 쥔 다음에 올바른 위치에 꽂아 놓는 방법으로 한다면 모든 책을 꺼내어 놓을 공간은 필요하지 않다. 책 한권 만큼의 공간만 필요할 것이다.
out-of-place
책을 모두 꺼내서 바닥에 내려놓는 경우엔 추가적으로 필요한 저장공간은 모든 책의 크기와 같다.
즉 자료구조의 크기와 같을 것이다.
이를 out-of-place 정렬이라고 한다.
out-of-place 정렬은 자료구조의 복사본을 순서대로 정렬하는 방법이다.
in-place
책을 한 손에만 쥐고 손에 쥔 책만 올바른 위치에 꽂아 놓는 정렬을 in-place 이라고 한다.
in-place 정렬은 자료구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬하는 방법이다.
또 다른 경우를 생각해보자.
중복된 요소가 있는 경우엔 정렬을 어떻게 해야할까?
안정 정렬
위 그림을 보면 중복된 숫자 1과 8있다.
정렬 후 첫번째 1은 두번째 1보다 항상 앞에있다.
역시 첫번째 8이 두번째 8보다 앞에 정렬된다.
중복된 숫자의 순서는 정렬을 하기 전과 같은 정렬을 안정 정렬이라고한다.
불안정 정렬
불안정 정렬은 안정 정렬과 반대의 개념이다.
모든 책을 바닥에 꺼내서 다시 꽂아 놓는경우를 다시 생각해보자.
만약 같은 책이 두 권 있다면 다시 꽂을 때 원래의 순서와 동일하게 꽂는다는 보장을 할 수 없다.
