소개 모든 노드가 힙 속성 (각 노드의 값이 자신의 자식노드 값보다 크거나 [최대 힙] 작은 [최소 힙] 완전 이진 트리) 을 만족하도록 재귀적으로 트리 구조를 만들어 정렬한다. 추가적인 메모리를 필요로 하지 않으면서 항상 \(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..
소개 현재 인덱스 위치 값과 이미 정렬된 부분 배열의 값들과 비교하여 들어갈 위치를 찾아 정렬한다. 성능이 좋아 다른 알고리즘의 일부로도 사용한다. 해당 삽입 지점 이후 배열 값들이 한 칸씩 밀리기 때문에 배열 길이가 길수록 효율이 떨어진다. 과정 코드 첫 번째 인덱스 \(nums[i = 0]\) 의 값은 정렬되어 있다고 가정하고 시작한다. compidx를 이용하여 \(i\) 인덱스의 값이 들어갈 인덱스를 정렬된 부분 배열 구간 (\(0\) ~ \(i - 1\)) 에서 찾는다. public static void main(String[] args) { int[] nums = { 3, 7, 2, 5, 1, 4 }; int len = nums.length; for (int i = 1; i < len; ++i)..
소개 배열을 조회하면서 현재 위치에 들어갈 값 (남은 숫자들 중 가장 크거나 작은 값) 을 찾아 정렬한다. 과정 코드 현재 위치 \(i\) 값과 배열의 나머지 모든 값을 비교하여 가장 작은 값을 가진 인덱스 \(idx\) 를 \(j\)로 갱신한다. 두 번째 for문이 끝나면 \(i\)와 \(idx\) 위치의 값을 바꾼다. public static void main(String[] args) { int[] nums = { 8, 5, 2, 6, 9, 4, 1, 3, 0, 7 }; int len = nums.length; for (int i = 0; i ..
소개 배열의 인접한 두 요소 값들을 비교하여 정렬한다. 과정 코드 \(j\) 인덱스 값이 \(j + 1\) 인덱스 값보다 크다면 두 숫자의 위치를 바꿔준다. 첫 번째 for문이 한 번 종료될 때마다 가장 마지막 인덱스에 숫자가 하나씩 정렬된다. public static void main(String[] args) { int[] nums = { 6, 7, 2, 8, 1, 4 }; int len = nums.length; for (int i = 0; i nums[j + 1]) Swap(nums, j, j + 1); } } } 결과 계산 복잡도 Time Complexity : for..
보호되어 있는 글입니다.
보호되어 있는 글입니다.