안정 정렬
-
선택 정렬이 불안정 정렬인 이유 :: 마이구미알고리즘 2017. 1. 13. 00:07
이번 글은 선택 정렬이 불안정 정렬인 이유에 대해 다뤄본다.그에 앞서 증명을 위해 버블 정렬, 선택 정렬, 삽입 정렬을 언급하겠다. 3가지를 드는 이유는 특별한 건 없다.단지 가장 구현하기 쉽고, 이해하기 쉬운 정렬이기 때문이다.(세가지 모두 시간 복잡도는 O(n^2) 이다.) 버블 정렬 선택 정렬 삽입 정렬세가지 정렬은 어렵지 않기 때문에 위키의 도움을 빌리겠다. 안정 정렬과 불안정 정렬이라는 말을 들어봤을 것이다.안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )불안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 선택 정렬 )위와 같이 무슨 뜻인지만 알고 있는 경우가 많다.왜? 질문을 던지면 선뜻 증명을 못하면 문제가 있다.많은 글..