선택 정렬이 불안정 정렬인 이유 :: 마이구미
이번 글은 선택 정렬이 불안정 정렬인 이유에 대해 다뤄본다.
그에 앞서 증명을 위해 버블 정렬, 선택 정렬, 삽입 정렬을 언급하겠다.
3가지를 드는 이유는 특별한 건 없다.
단지 가장 구현하기 쉽고, 이해하기 쉬운 정렬이기 때문이다.
(세가지 모두 시간 복잡도는 O(n^2) 이다.)
세가지 정렬은 어렵지 않기 때문에 위키의 도움을 빌리겠다.
안정 정렬과 불안정 정렬이라는 말을 들어봤을 것이다.
안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )
불안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 선택 정렬 )
위와 같이 무슨 뜻인지만 알고 있는 경우가 많다.
왜? 질문을 던지면 선뜻 증명을 못하면 문제가 있다.
많은 글들에서도 왜?라는 질문에 대한 답을 다루지 않는다.
본인은 Why를 배우지 않고 What을 배우고 있기 때문이지 않을까 생각한다.
이제 불안정 정렬이란 어떤 예이고, 선택 정렬이 왜 불안정 정렬인지 보자.
중복 숫자의 경우가 있기에 설명의 편의를 위해 수를 알파벳으로 나타내겠다.
Array - <B> <b> <a> <c> ( a < b < c )
b와 B는 같은 수다. (b == B)
(숫자로 나타내면 2 2 1 3 이라고 보면 된다.)
선택 정렬 시 위의 결과는 아래와 같다.
Array - <a> <b> <B> <c> ( a < b < c )
b 와 B는 동일한 수였지만 B가 순서로 보자면 b 보다 앞서 있었다.
하지만 선택 정렬 후 B가 b보다 뒤로 배치되면서 순서가 바뀌었다.
이렇게 순서가 유지되지 않는 경우를 불안정 정렬이라함으로써 선택 정렬은 불안정 정렬이 되는 것이다.
누군가에게 가르쳐주는 입장에서 생각해보자.
그러면 Why를 기반으로 설명을 해줘야하기 때문에 초급자에게는 도움이 될 수 있겠다는 생각이 들어 다뤄보았다.
이만 안녕.
Why is selection sort not stable?
http://stackoverflow.com/questions/4601057/why-is-selection-sort-not-stable