분류 전체보기26 Quick sort 퀵정렬은 최악의 경우 O(n^2)의 수행시간으로, 평균 O(n log n)의 수행시간으로 배열을 정렬하는 알고리즘이다. O(n log n) 내에 숨겨진 상수인자가 매우 작아 속도 면에서 매우 효율적이며, 내부 정렬로 작동하기 때문에 실제 문제에서 가장 유용한 정렬 방법 중 하나이다. (내부정렬이란, 정렬하고자 하는 배열 이외의 추가적인 배열공간을 필요로 하지 않는 것을 의미한다.) 퀵정렬은 사전에 배열이 보다 많이 정렬되어 있을수록, 배열 내의 겹치는 원소 수가 많아질 수록 수행시간이 O(n^2)에 가까워진다. 이에 대한 자세한 내용은 후술한다. 퀵정렬은 divide&conquer방식으로 작동한다. A[first~last]의 본래 배열을 A[first~mid-1] A[mid+1~ last]로 분할한다. .. 2022. 7. 4. HEAP Heap이란 용어는 본래 힙정렬로부터 나온 말이다. 프로그래밍 언어가 제공하는 공간개념인 Heap 역시 이 자료구조에서 유래한 표현이다. Heap 자료구조란 complete binary tree를 배열로 구현한 형태의 자료구조를 의미한다. complete binary tree를 기반으로 하기 때문에 원소의 갯수가 n인 heap의 높이는 O(log n)이다. ary의 index 1부터 배열을 채우기 시작한다. 부모, 자식노드는 일반적으로 다음 매크로/인라인을 통해 구현한다 #define PARENT(i) (i>>1) #define LEFT(i) (i 2022. 7. 1. 이전 1 2 3 4 5 다음