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]

이진 트리

• 최대 자식 노드 2개를 갖는 트리

• 풀 이진트리, 모든 레벨에 노드들이 꽉찬 형태

• 완전 이진 트리, 마지막 레벨을 제외하면 꽉차고, 왼쪽부터 채워져 있어야함

MAX-HEAPIFY

• 전체를 힙으로 만들기

• 하위 구조 반복 -> 재귀 활용

• 루트 < 자식 선택 -> 스왑 (왼,오)

// 힙정렬
  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)

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);
}