# 3. 정렬 선택정렬 * **O(n^2)** * 비교 -> 스왑 버블정렬 * **O(n^2)** * 앞뒤 비교 * 라스트에 최대 or 최소 위치 * 정렬된 마지막 제외, 같은 작업 반복 삽입정렬 * **O(n^2)** * 뒤에서 찾아가는게 좀 더 효율적 -> 삽입 위치에서 오른쪽으로 하나씩 밀려야하므로 합병정렬 (머지소트) * 나누고 -> 재귀 * 정렬 된 2개의 배열 합병 -> 전체 정렬 * 전반 + 후반 + 전체머지 -> T(N/2) + T(N/2) + N -> **O(NlogN)** 퀵 정렬 * 최악의 경우 : 이미정렬된 데이터 -> 마직을 피봇으로 선택하는 경우 * n개, n-1개 ... 1개 시도 (피봇위치가 하나씩 뒤에서 앞으로 감, 분할의 횟수 ) * 항상왼쪽은 0, 오른쪽은 n-1개로 분할되는 경우 * 최선의 경우 : 항상 절반으로 분할 되는경우 * **O(NlogN)** 6\. 힙정렬 * 시간 복잡도 O(h) -> h는 레벨 * 노드 수 N -> h = 세타(logN) * 추가 배열 불필요 * **이진 힙 자료구조**를 사용 * 완전 이진트리 * heap property 를 만족해야함 (크기, 일관성) * 부모는 자식보다 크거나 같다 * 또는 부모는 자식보다 작거나 같다 * 최악의 경우, 시간 복잡도 **O(NlogN)** * 동일한 데이터를 가진 서로 다른 힙. 즉 힙은 유일하지 않고, 서로 다른 여러가지가 존재 할 수 있음 * **힙은 1차원 배열로 표현 가능** -> 너비 우선탐색, 너비우선으로 저장 * **완전 이진트리라 가능** * **인덱스로 추적이 가능** * A\[1...N] : N (노드의 개수) * 루트노드 A\[1] * A\[i]의 부모 = A\[i/2] * A\[i]의 왼쪽 자식 = A\[2i] * A\[i]의 오른쪽 자식 = A\[2i+1] ![](/files/-MEWTKt7NOZa-o0I13gW) #### 이진 트리 * 최대 자식 노드 2개를 갖는 트리 * 풀 이진트리, 모든 레벨에 노드들이 꽉찬 형태 * 완전 이진 트리, 마지막 레벨을 제외하면 꽉차고, 왼쪽부터 채워져 있어야함 #### MAX-HEAPIFY * 전체를 힙으로 만들기 * 하위 구조 반복 -> **재귀 활용** * 루트 < 자식 선택 -> 스왑 (왼,오) ```java // 힙정렬 public void maxHeapify_recur(int[] heapArr, int rootIdx) { // 1. 자식이 없다면 종료 // 2. 자식중 큰 놈 index k 리턴 // 3. 부모와 자식 비교 -> 부모 >= 자식 이면 종료 // 4. 아니라면 교환 (exchange) heapArr[rootIdx] and heapArr[k] // 5. 다시 재귀 maxHeapify_recur(heapArr, k) } // public void maxHeapify_iter(int[] heapArr, int rootIdx) { // while heapArr[rootIdx] has a child do // k = index of the biggest child of // if heapArr[rootIdx] >= heapArr[k] return (종료) // else : exchange heapArr[rootIdx] and heapArr[k]; // -> rootIdx = k (자식을 루트로 설정) end } ``` #### 정렬할 배열을 힙으로 만들기 MAX-heapify(A) - 시간 복잡도 O(N) * heap-size\[A] <- length\[A] (정렬할 데이터의 개수) * 2/i(부모) -> i(나) -> 2i(왼), 2i+1(오) * for i <- \[length\[A]/2] down to 1 do MAX-heapify(A,i) 1. 주어진 데이터로 힙을 만든다 (힙은 어느정도 크기가 정해진다) 2. 최대 or 최소는 루트에 배치되게 된다 (맨앞) 3. 2번을 이용하여 정렬 4. 맨처음(최대, 최소)와 맨마지막 데이터와 스왑 -> pop -> 다시 힙구조 정리 5. 루트에 대해 Heapify -> maxHeapify(1) (1:rootIdx, 배열에서는 0으로 하도) #### **우선순위큐** * 힙응용 (최대, 최소 우선순위큐) * 시간복잡도 O(logN) ```java MAX-HEAP-INSERT(A, key) heap_size = heap_size+1; i = heap_szie; // 문제아 노드 while(i > 1 and A[parent(i)] < A[i]) { exchange A[i] and A[parent(i)]; i = parent(i); } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://ssosso.gitbook.io/study/dev-build-up/undefined-1/3..md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.