천천히 가는 것을 걱정하지 말고 서있는 것을 걱정하라.

기수 정렬 (Radix Sort) ? 기수 정렬은 각 자리 위치를 하나씩 증가시키면서 숫자들을 정렬하는 방법이다. 안정 정렬에 속하며, 카운팅 정렬과 마찬가지로 값의 비교연산 없이 정렬한다. 기수 정렬의 단점은 다음과 같다. 제자리 정렬이 아니기 때문에 추가적인 메모리가 필요하다. 동일한 길이를 가진 숫자나 문자열이여야 한다. 정렬하는 숫자 자릿수 \(k\) 에 따라 \(O(kn)\) 의 시간 복잡도를 가진다. 기수 정렬 과정은 다음과 같다. 1의 자리 숫자를 비교해서 오름차순 또는 내림차순으로 정렬한 뒤, 큐 버킷에 삽입한 뒤 순서대로 뽑아 정렬한다. 그 다음, 10의 자리 숫자를 비교해서 동일하게 수행한다. 가장 큰 숫자의 자릿 수만큼 반복해서 수행한다. Code public static void r..

정렬 기법 비교 Stable : 동일한 값에 대해 순서가 뒤바뀌지 않고 정렬 (먼저 등장한 동일한 값이 정렬 후에도 먼저 등장) In-Place : 새로운 배열을 만들 필요 없이 입력 배열 내부에서 정렬 Comparison : 배열 내 요소값들을 서로 비교하여 정렬 Bucket 정렬의 경우, 각 Bucket에 대해 어떤 정렬 알고리즘을 사용하느냐에 따라 Comparison 유무가 달라질 수 있다. Algorithm Stable In-Place Comparison 최선 (Best) 평균 (Average) 최악 (Worst) Bubble O O O $O(N^2)$ $O(N^2)$ $O(N^2)$ Selection O O O $O(N^2)$ $O(N^2)$ $O(N^2)$ Insertion O O O $O(N..

Lower Bound 찾고자 하는 target 이상의 값이 인덱스 0부터 시작했을 때 등장하는 최초의 위치 과정 코드 public static int lowerBound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; // 찾으려고 하는 target 값이 현재 nums[mid] 값보다 작거나 같다면 // nums[mid]는 후보가 될 수 있는 값이다. if (target

소개 요소 값들끼리 서로 비교하지 않고 정렬하는 알고리즘이다. 배열 내 최대 값 + 1 만큼의 길이 배열이 필요하기 때문에 메모리가 낭비될 수 있다. 애니메이션 : URL 과정 1. 먼저 배열 내에 원소 값들의 갯수를 저장하는 카운팅 배열 (Counting Array) 를 만든다. 2. Counting Array (c[])의 요소들에 대해서 직전 요소들의 값을 더해준다. 3. 입력 배열과 동일한 크기의 출력 배열 (b[])을 만들고, 입력 배열의 역순으로 출력 배열에 요소들을 채워 넣어준다. 여기서 우리는 두 값을 비교하는 과정 없이 정렬이 수행되는 것을 알 수 있다. 코드 public static void main(String[] args) { final int MAX = 5; int[] nums = ..

소개 한쪽의 배열에 포함된 값이 다른 쪽 배열의 값보다 항상 작도록 배열을 분할한다. 이를 수행하기 위해 파티션 (Partition) 이란 단계를 수행한다. 파티션 (Partition) ? - 배열에 있는 수 중 임의의 '기준 수 (Pivot)' 를 지정한 후, 이 기준 수 보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다. Pivot에 따라 시간복잡도가 크게 달라진다. 과정 코드 public static int Partition(int[] nums, int left, int right) { int mid = left + (right - left) / 2; Swap(nums, left, mid); int l = left + 1, r = right; int pivot = nums[l..

소개 모든 노드가 힙 속성 (각 노드의 값이 자신의 자식노드 값보다 크거나 [최대 힙] 작은 [최소 힙] 완전 이진 트리) 을 만족하도록 재귀적으로 트리 구조를 만들어 정렬한다. 추가적인 메모리를 필요로 하지 않으면서 항상 \(O(NlogN)\) 을 보장한다. 시간 복잡도가 \(O(NlogN)\) 이지만 실제로는 동일한 시간 복잡도를 가진 다른 정렬 알고리즘 (ex. Quick Sort) 보다 느리다. 힙 (Heap) vs 이진 탐색 트리 (Binary Search Tree) 공통점 : 완전 이진 트리로 구성된다. 차이점 : 힙 부모 노드가 자식 노드 보다 크거나 작은 속성을 만족한다. 각각 최대 힙과 최소 힙이라 부른다. 정렬에 강점을 가지고 있다. 이진 탐색 트리 왼쪽 자식 노드는 부모 노드보다 작고..

소개 주어진 배열을 절반으로 나눠 비슷한 크기를 가진 두 개의 배열을 만든 뒤 정렬한다. 평균적으로 \(O(NlogN)\) 의 준수한 성능을 낸다. 정렬한 배열을 담을 추가적인 메모리가 필요하다. 과정 코드 public static void Merge(int[] nums, int left, int mid, int right) { int l = left, r = mid + 1; int idx = left; int[] sorted = new int[nums.length]; for (int i = left; i

소개 삽입 정렬의 '배열이 어느정도 정렬되어 있을 때 속도가 빠르다'는 장점을 이용한다. 삽입 정렬의 문제점은 요소값들을 삽입할 때 이웃한 위치로 한 칸씩 이동한다는 것이다. 만약 삽입할 요소위치가 현재 위치보다 먼곳에 있다면 불필요한 반복과 비교가 수행된다는 것이다. 이러한 점을 보완하여 셀 정렬은 배열을 한 번에 정렬하지 않는다. 일정한 기준에 따라 먼저 정렬해야 할 배열을 여러 개의 부분 배열로 만들고, 각 부분 배열을 삽입 정렬을 이용하여 정렬한다. 간격 (gap) 이라는 값 (길이 / 2 or 길이 / 3 + 1 ) 을 통해 부분 배열을 만든다. 길이 / 2 길이 / 3 + 1 gap이 짝수일 경우 +1 하여 홀수로 만드는 것이 좋다고 한다. (나누는 간격에 의해 성능이 좌우) 과정 코드 pub..