정렬 알고리즘 썸네일형 리스트형 병합 정렬(Merge Sort) 병합 정렬(Merge-Sort) - 배열의 원소를 완전 분해한 후에 다시 병합하며 정렬하는 방식 - 항상 O(n log n)의 복잡도를 가진다 1. 동작 원리 (1) 주어진 배열을 2개의 파티션으로 나눈다. (2) 하나의 원소가 남을 때까지 (1)의 과정을 재귀적으로 반복한다. (3) 완전 분해한 원소를 다시 병합하며 정렬을 수행한다. 2. 함수 설명 - merge_sort() : 동작원리 (1)과 (2)에 해당하는 기능을 수행한다. - merge() : 동작원리 (3)에 해당하는 기능을 수행한다. #include #include #include #include #define MAX 10 // size of array #define INF 10000 // infinity value void display.. 더보기 힙 정렬(Heap Sort) 힙 정렬(Heap-Sort) - 최대 힙 트리 또는 최소 힙 트리를 구성해 정렬하는 방식 - 일반적으로 O( n log n)의 복잡도를 가진다. ( 퀵 정렬은 최악의 경우 O(n²)의 복잡도를 가지기 때문에 힙 정렬이 선호된다.) 동작 원리 1. 최대(최소) 힙을 구성한다. 자노드를 가진 부노드부터 구성하며, 아래부터 루트까지 순차적으로 구성한다. 2. 루트에 위치한 수와 가장 작은 수를 교환한다. 3. 교환한 수를 제외하고 힙의 특성을 유지시킨다. 4. 위의 2와 3 과정을 반복한다. 함수 설명 - heap_sort() : 동작 원리 "2"의 과정을 수행하는 함수 - build_max_heap() : 동작 원리 "1"의 과정을 수행하는 함수로 기본적인 힙의 구조를 구성한다. - max_heapify().. 더보기 퀵 정렬(Quick Sort) 1. 퀵 정렬(Quick-Sort) - 퀵 정렬의 내부 루프는 대부분 컴퓨터의 아키텍처에서 효율적으로 작동하도록 설계되어 있다. ( 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높기 때문 ) - 일반적으로 퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행한다. ( 최악의 경우 O(n²) ) - 정렬을 위해 작은 공간( O(log n) )의 메모리를 필요로 한다. 2. 동작 원리 1. 리스트의 중간 원소를 피벗으로 지정한다. 2. 피벗을 기준으로, 앞에는 피벗보다 값이 작은 원소들을 배치하고 뒤에는 피벗보다 값이 큰 원소들을 배치한다. ( 이렇게 리스트를 나누는 것을 "분할(partition)"이라고 한다. ) 3. 분할된 두 개의 리스트에 대해 재귀적으로 이 과정을 반복한다. #i.. 더보기 이전 1 다음