알고리즘 문제를 해결하기 위한 정렬(Sort) 방법

정렬은 주어진 숫자들을 오름차순이나 내림차순으로 재배열하는 것을 뜻한다. 알고리즘 문제를 풀다 보면 특정 정렬을 구현하는 문제도 매우 많은 편이고 실제로도 중요하다. 정렬방법은 크게  버블, 선택, 삽입, 퀵, 병합, 기수 정렬 이렇게 6가지로 분류할 수 있다. 물론 큰 개념만 그런 것이고 세부적으로는 다양한 변형들이 존재하고 문제를 풀 때에도 보통 변형해서 사용해야만 풀리는 경우가 많다.

그러면 어떤 정렬방법을 사용하는 것은 어떻게 결정하는가? 각 방법들은 일반적 성능, 점유 메모리, 특정 상황에서의 성능에 따라 알맞게 써야 한다. 성능은 정렬을 시행하는 데 걸리는 시간을 말하며 빅 오 표기법으로 표현한다. 일반적인 성능(평균 성능)은 랜덤한 숫자를 정렬할 때 모든 수를 정렬하는데 걸리는 시간을 말한다. 보통 O(n^2) < O(nlogn) < O(n) < O(1) 이 정도로 구분되는 편이다. 아마 일반적으로 사용할 때는 O(nlogn) 시간복잡도를 가지는 퀵 정렬이나 병합정렬 정도가 한계이지 않나 싶다. O(n) 시간복잡도를 가지는 기수정렬은 숫자들의 자릿수를 변수로 처리해 혼자 자릿수가 엄청 긴 수가 있으면 성능이 급락한다. 이러한 제약조건 없이 '일반적인' 상황에서는 보통 퀵 정렬을 많이 사용하고 자바의 기본 내장함수인 Arrays.sort() 도 이중피벗 퀵 정렬을 사용한다. 만약 정렬 문제인데 모든 수를 정렬해야 한다면 일단 기본함수먼저 시도해 보는 것도 나쁘지 않다. 처음에는 퀵 이라길래 이게 가장 좋은 건줄 알았다

하지만 각 정렬의 최악의 경우에는 보통 O(n^2)으로 성능이 하락하기 때문에 문제에 맞는 정렬 방법을 선택하고 약간의 수정을 해야 한다. 예를 들어 정렬 후 k번째 수를 출력하세요.라는 문제는 어떤 방법이 가장 효율적인가? 그냥 전부 정렬한 뒤 출력하면 되지 않느냐고 할 수도 있지만 아마 시간초과가 뜰 것이다. 이 경우 퀵 셀렉션 정렬이라는 퀵 정렬의 변형된 방법을 이용하는 것이 가장 좋다. 이것은 나중에 알아보고 다음 포스팅부터 정렬 방법들을 하나씩 알아보자.