C#의 힙 정렬

힙 정렬은 힙 데이터 구조를 사용하는 정렬 알고리즘입니다. 힙의 루트 요소, 즉 가장 큰 요소가 제거될 때마다 배열에 저장됩니다. 가장 오른쪽 리프 요소로 대체된 다음 힙이 다시 설정됩니다. 이것은 힙에 더 이상 요소가 남지 ​​않고 배열이 정렬될 때까지 수행됩니다.

C#에서 힙 정렬을 보여주는 프로그램은 다음과 같습니다.

예시

using System;
namespace HeapSortDemo {
   public class example {
      static 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--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
         }
      }
      static 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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
         }
      }
      public static void Main() {
         int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
         int n = 10, i;
         Console.WriteLine("Heap Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         heapSort(arr, 10);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

출력

위 프로그램의 출력은 다음과 같습니다.

Heap Sort
Initial array is: 55 25 89 34 12 19 78 95 1 100
Sorted Array is: 1 12 19 25 34 55 78 89 95 100

이제 위의 프로그램을 이해해보자.

main() 함수는 배열 arr를 포함합니다. 초기 배열을 인쇄한 다음 배열을 정렬할 함수 heapSort()를 호출합니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.

int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
heapSort(arr, 10);

heapSort() 함수는 먼저 주어진 요소를 힙으로 변환합니다. 이것은 for 루프를 사용하고 힙의 잎이 아닌 모든 요소에 대해 heapify() 함수를 호출하여 수행됩니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.

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

힙이 생성된 후 for 루프를 사용하여 힙의 루트 요소, 즉 가장 큰 요소를 제거합니다. 가장 오른쪽 리프 요소로 대체된 다음 heapify()가 다시 호출되어 힙을 재설정합니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.

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

heapify() 함수는 필요에 따라 요소를 배열하여 힙 구조를 만듭니다. 이 프로세스는 인덱스 i의 요소에서 시작하므로 heapify() 함수의 루트 요소로 간주됩니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.

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) {
   int swap = arr[i];
   arr[i] = arr[largest];
   arr[largest] = swap;
   heapify(arr, n, largest);
}

마지막으로 정렬된 배열이 main() 함수에 표시됩니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}