[알고리즘 공부] 힙 정렬, 계수 정렬 (C언어)

힙 정렬

힙을 이용해 데이터를 정렬

전체 시간 복잡도: O(N*logN)

- 데이터 개수가 N개일 때 N/2개의 데이터에만 힙생성 알고리즘(Heapify)를 적용해주면 최대힙이 만들어짐. 
   사실상 O(N*logN) ≓ O(N/2*logN)

=> 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘. 고급 프로그래밍 기법으로 갈수록 힙의 개념이 자주 등장하기 때문에 반드시 알고 넘어가야 함.
힙 트리 구조를 이용하는 정렬 방법. 병합정렬과 달리 별도로 추가적인 배열이 필요하지 않기 때문에 메모리 측면에서 몹시 효율적.
항상 O(N*logN)을 보장할 수 있다는 점에서 강력한 정렬 알고리즘. 이론적으로는 퀵/병합 정렬보다 효율적이라고 할 수 있음. 하지만 속도만 가지고 비교하면 평균적으로 퀵 정렬이 더 빨라서 힙 정렬이 일반적으로 많이 사용되지는 않음.

• 완전 이진 트리: 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리. 노드가 중간에 비어있지 않고 가득 참.
  
  
• 힙: 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리. 힙 정렬을 하기 위해서는 정해진 데이터가 힙 구조를 가지도록 만들어야 함.
  
  
• 최대 힙: 부모노드가 자식노드보다 큰 힙
  특정 노드 때문에 최대 힙이 붕괴되기도 함. 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm)을 사용

 

힙 생성 알고리즘(Heapify): 특정한 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘.
특정한 하나의 노드에 대해서 수행. 하나의 노드를 제외하고는 최대힙이 구성된 상태라고 가정. 위치를 바꾼 뒤에도 또 자식 중에 더 큰 자식이 있으면 자신과 위치를 바꿔야 함.

힙 생성 알고리즘의 시간 복잡도: O(logN)

데이터 개수에 log2를 씌우고 올림 처리. ( ex. n=5, log2(5) = 2.x => 3) 
모든 정점에 대해 Heapify를 적용하게 되면 높이(log2(n)) * 모든정점(n) => (실제로는 n/2 정점에 대해서만 수행해도 모두 힙이 됨)

 

#include <stdio.h>

int number = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};

int main() {
    // 먼저 전체 트리 구조를 최대 힙구조로 바꾼다.
    for(int i=1; i<number; i++) {
        int c = i;
        do {
            int root = (c-1) / 2;
            // 부모가 자식보다 작으면 위치 바꿔주기
            if(heap[root] < heap[c]){
                int tmp = heap[root];
                heap[root] = heap[c];
                heap[c] = tmp;
            }
            c = root;
        } while (c != 0);
    }
    // 크기를 줄여가며 반복적으로 힙을 구성
    for(int i = number-1; i >= 0; i--) {
        int tmp = heap[0];
        heap[0] = heap[i];
        heap[i] = tmp;
        int root = 0;
        int c = 1;
        do { 
            c = 2*root + 1;
            // 자식 중에 더 큰 값 찾기
            // 범위를 벗어나지 않으면서, 왼쪽과 오른쪽 중 더 큰 값을 c에 담도록 함.
            if(c < i-1 && heap[c] < heap[c+1]) {
                c++;
            }
            // 루트보다 자식이 더 크다면 교환
            if(c < i && heap[root] < heap[c]) {
                int tmp = heap[root];
                heap[root] = heap[c];
                heap[c] = tmp;
            }
            root = c;
        } while (c < i);
    }
    for(int i = 0; i < number; i++) {
        printf("%d ", heap[i]);
    }

    return 0;
}

 

- Heapify는 n/2의 내림 만큼만 보면 힙 구조가 됨. 힙구조를 짤 때는 상향식, 하향식 중 본인 코딩 스타일에 맞게 하면 됨.

- Heapify를 한번 수행하고 나면 가장 큰 값이 루트에 올라가 있음. 이를 마지막 원소와 자리를 바꾸고 마지막 원소를 제외한 나머지 원소끼리 또 Heapify 수행 후 루트를 가장 마지막 값과 위치를 바꾸길 반복.

 

계수 정렬

크기를 기준으로 개수 세기

시간 복잡도 : O(N)

=> 범위 조건이 있는 경우에 한해 굉장히 빠른 알고리즘. 위치를 바꿀 필요 없이 개수를 센 후 그 개수만큼 출력하면 됨.
전체 데이터의 크기만큼 다 허용할 수 있는 크기의 배열을 만들어줘야 한다는 점에서 크기가 한정돼있는 데이터에 한해서 정렬 수행 가능.
데이터가 한 개라도 크게 뛰면 배열 크기를 크게 잡아야 하기 때문에 정렬할 데이터 자체의 크기에 매우 의존을 많이 받음.

• 매우 빠르지만 자주 사용할 수 있는 케이스는 아님. 데이터의 크기가 한정돼있을 때만 사용하기 좋기 때문.

 

#include <stdio.h>

int main() {
    int tmp;
    int cnt[5] = {0,};
    int array[30] = {
        1,3,2,4,3,2,5,3,1,2,
        3,4,4,3,5,1,2,3,5,2,
        3,1,4,3,5,1,2,1,1,1
    };
    for(int i=0; i<30; i++) {
        cnt[array[i] - 1]++;
    }
    for(int i=0; i<5; i++) {
        if(cnt[i] != 0) {
            for(int j=0; j < cnt[i]; j++) {
                printf("%d", i+1);
            }
        }
    }

    return 0;
}