> For the complete documentation index, see [llms.txt](https://ssosso.gitbook.io/study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ssosso.gitbook.io/study/dev-build-up/undefined-1/3..md).

# 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
  }
```

#### 정렬할 배열을 힙으로 만들기&#x20;

MAX-heapify(A) - 시간 복잡도 O(N)&#x20;

* 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 -> 다시 힙구조 정리&#x20;
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);
}

```