특징 1. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균, 최악 시간 복잡도O(N * logN) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 힙(Heap) 자료구조를 이용하여 정렬한다. 힙은 마지막 depth를 제외하고 모든 노드가 왼쪽부터 채워져있는 완전 이진 트리 구조이며, 제일 큰 수나, 제일 작은 수를 빠르게 뽑아낼 수 있도록 하는 자료구조다. 최대힙은 트리의 노드 중 최댓값이 루트 노드에 존재하며, 최소힙은 트리의 노드 중 최솟값이 루트 노드에 존재한다. 힙정렬은 최대힙과 최소힙으로 모두 구현 가능하지만, 본 포스팅은 최대힙으로 진행한다. 완전 이진트리는 위와 같이 배열로 표현할 수 있다. 혹은 배열을 위와 같은 완전 이진 트리로..

특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균 시간 복잡도O(N * logN), 최악 O(N^2) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 1. 버퍼의 요소 중 하나를 피벗(pivot)으로 지정 보통 맨 왼쪽, 중앙, 맨 오른쪽으로 지정하고, 본 포스팅은 피벗을 맨 왼쪽으로 함 2. 피벗보다 작은 값을 피벗의 왼쪽으로 이동, 피벗보다 큰 값을 피벗의 오른쪽으로 이동 3. 피벗을 기준으로 왼쪽 버퍼와 오른쪽 버퍼를 나누어 각 재귀 함수 호출 구현에서 중요한 점은 퀵 정렬은 추가 버퍼를 사용하지 않는 In-place sort라는 것이다. 따라서 2번 과정에서 새로운 버퍼를 이용하지 않고, 한 버퍼에서 s..

# 합병 정렬 특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬 3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN) 4. 임시 버퍼의 필요로 공간 복잡도 O(N) 알고리즘 1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출 2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환 3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사 (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가) 4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사 구현 및 상세 설명 #include void sort(std::vector& buf) { std::vector ..