아무 말

들어가기에 앞서.. 단순히 빠른 정렬 방법이 아니라, 특정 상황에서 좋은 정렬법에 대해 설명하고자 한다. BOJ의 '수 정렬하기(시리즈)'의 문제들을 통해 여러 정렬의 방법들을 알아보고자 한다. 본론 2750번: 수 정렬하기는 다루지 않도록 하겠다. 먼저, 10989번: 수 정렬하기 3을 보자. 딱 봐도 Counting Sort의 냄새가 난다. 시간 복잡도는 수의 범위의 크기가 T일 때, O(T+N)이다. Counting Sort는 정렬하고자 하는 수를 배열의 index로 생각하고 배열에서 Count 한 뒤 Count 한 횟수만큼 출력하는 것으로 이루어진다. Counting Sort를 모르는 사람은 많지 않을 것으로 생각한다. 이 Counting Sort의 단점은 수의 범위가 클 때 처리하기 어렵다는 것..

간단한 설명 병합 정렬은 존 폰 노이만에 의해 고안된 알고리즘이다. 병합 정렬은 분할정복 기법을 이용하며 다음과 같이 작동한다. 분할: 정렬할 n개 원소의 배열을 n/2개 씩 부분 수열 두 개로 분할한다. 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다. 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다. 계속해서 분할을 하다 보면 원소의 수가 하나가 되고 이는 원소가 하나임으로 이미 정렬된 수열이다. 이 하나의 원소로 이루어진 부분수열로 부터 각 부분수열을 병합해가면서 정렬하는 알고리즘이 바로 병합 정렬이다. 알고리즘의 설계 알고리즘의 설계를 위해 트리를 하나 생각해보자. 이 트리의 각 정점에는 두 개의 자식노드가 있고(물론 한개의 자식만 가질수도 있다.) 맨 아래쪽의..

삽입 정렬은 수를 정렬된 상태로 삽입함으로서 정렬하는 방법이다. A라는 배열이 있을 때 {A[1]}을 초기에 정렬된 배열이라고 하고 이 배열의 처음부터 끝까지를 확인하면서 A[i]보다 큰 수가 나오면 그 자리에 A[i]를 삽입한다. 이때 원래 자리에 있던 수를 비롯한 A[i]보다 큰 수들은 한 칸씩 뒤로 밀리게 된다. 또한 이 정렬된 배열을 따로 만들지는 않으며, A의 앞부분에 나타낸다. INSERTION-SORT(A) for j=2 to A.length key=A[j] i=j-1 while i>0 and A[i]>key A[i+1]=A[i] i=i-1 A[i+1]=key 위는 배열 A에 대한 삽입 정렬의 의사코드이다. A.length는 수의 개수이고 key는 현재 정렬해야하는 수를 의미한다. 삽입정렬에..