동적 배열을 사용한 힙 정렬 (Heap Sort)

소개

이 랩에서는 C++ 에서 동적 배열을 사용하여 힙 정렬 (Heap Sort) 알고리즘을 구현하는 방법을 배우게 됩니다. 힙 정렬은 비교 기반 정렬 알고리즘으로, 입력을 정렬된 영역과 정렬되지 않은 영역으로 나누어 작동하며, 가장 크거나 작은 요소를 추출하여 정렬된 영역으로 이동시켜 정렬되지 않은 영역을 반복적으로 줄여나갑니다.

동적 배열 생성 (Creating the Dynamic Array)

다음 명령을 사용하여 ~/project 디렉토리에 main.cpp라는 새 파일을 생성합니다.

touch ~/project/main.cpp

먼저, 요소를 저장할 동적 배열을 생성합니다. 프로그램 실행 중에 new 연산자를 사용하여 동적으로 메모리를 할당합니다.

int* arr;
arr = new int[size];

Heapify 함수

다음으로, 배열의 요소를 재정렬하기 위해 heapify() 함수를 생성합니다. heapify() 함수의 목적은 힙 속성 (heap property) 을 유지하는 것입니다. 이는 각 노드가 자식 노드보다 크거나 같음을 의미합니다.

void heapify(int* arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

힙 정렬 함수 (Heap Sort Function)

heapify() 함수를 구현한 후, 배열을 오름차순으로 정렬하기 위해 heapSort() 함수를 생성합니다.

void heapSort(int* arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

메인 함수 (Main Function)

마지막으로, 사용자로부터 요소를 읽고 힙 정렬 알고리즘을 사용하여 정렬된 배열을 표시하기 위해 main() 함수를 생성합니다.

int main() {
    int size;
    cout << "Enter the number of elements: ";
    cin >> size;

    int* arr;
    arr = new int[size];

    cout << "Enter the elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    heapSort(arr, size);

    cout << "Sorted Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

요약

이 랩에서는 C++ 에서 동적 배열을 사용하여 힙 정렬 (Heap Sort) 알고리즘을 구현하는 방법을 배웠습니다. 또한 동적 배열 생성, 배열 힙화 (heapifying), 그리고 배열을 정렬하여 오름차순으로 정렬된 배열을 표시하는 방법에 대해 배웠습니다. 지침에 따라 샘플 코드를 실행하고 힙 정렬 알고리즘 구현을 연습하십시오.