ヒープソートアルゴリズムを使用して10個の要素の配列をソートするC++プログラム

ヒープソートは、バイナリヒープデータ構造に基づいています。バイナリヒープでは、親ノードの子ノードは最大ヒープの場合はそれ以下であり、親ノードの子ノードは最小ヒープの場合はそれ以上です。

ヒープソートのすべてのステップを説明する例は次のとおりです。

並べ替え前の10個の要素を含む元の配列は-

この配列は、max-heapifyを使用してバイナリ最大ヒープに組み込まれています。配列として表されるこの最大ヒープは、次のように与えられます。

最大ヒープのルート要素が抽出され、配列の最後に配置されます。次に、max heapifyが呼び出され、残りの要素が最大ヒープに変換されます。これは、ソートされた配列が最終的に取得されるまで行われます。これは次のように与えられます-

ヒープソートアルゴリズムを使用して10個の要素の配列をソートするプログラムは次のとおりです。

例

#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
   int temp;
   int largest = i;
   int l = 2 * i + 1;
   int r = 2 * i + 2;
   if (l < n && arr[l] > arr[largest])
      largest = l;
   if (r < n && arr[r] > arr[largest])
      largest = r;
   if (largest != i) {
      temp = arr[i];
      arr[i] = arr[largest];
      arr[largest] = temp;
      heapify(arr, n, largest);
   }
}
void heapSort(int arr[], int n) {
   int temp;
   for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
   for (int i = n - 1; i >= 0; i--) {
      temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
      heapify(arr, i, 0);
   }
}
int main() {
   int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
   int n = 10;
i   nt i;
   cout<<"Given array is: "<<endl;
   for (i = 0; i *lt; n; i++)
   cout<<arr[i]<<" ";
   cout<<endl;
   heapSort(arr, n);
   printf("\nSorted array is: \n");
   for (i = 0; i < n; ++i)
   cout<<arr[i]<<" ";
}

出力

Given array is:
20 7 1 54 10 15 90 23 77 25
Sorted array is:
1 7 10 15 20 23 25 54 77 90

上記のプログラムでは、関数heapify（）を使用して要素をヒープに変換します。この関数は再帰関数であり、呼び出された要素、つまりこの場合はiから開始して最大ヒープを作成します。これを示すコードスニペットは次のとおりです。

void heapify(int arr[], int n, int i) {
   int temp;
   int largest = i;
   int l = 2 * i + 1;
   int r = 2 * i + 2;
   if (l < n && arr[l] > arr[largest])
      largest = l;
   if (r < n && arr[r] > arr[largest])
      largest = r;
   if (largest != i) {
      temp = arr[i];
      arr[i] = arr[largest];
      arr[largest] = temp;
      heapify(arr, n, largest);
   }
}

関数heapSort（）は、ヒープソートを使用して配列要素をソートします。非リーフノードから開始し、各ノードでheapify（）を呼び出します。これにより、配列がバイナリの最大ヒープに変換されます。これは次のように示されます-

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

この後、関数heapSort（）は、forループの各反復でルート要素を取得し、それを配列の最後に配置します。次に、heapify（）が呼び出され、残りの要素が最大ヒープであることを確認します。最終的に、このメソッドを使用してすべての要素が最大ヒープから取り出され、ソートされた配列が取得されます。これは次のように表示されます。

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

関数main（）では、最初に配列が表示されます。次に、関数heapSort（）が呼び出されて配列がソートされます。これは、次のコードスニペットによって提供されます。

cout<<"Given array is: "<<endl;
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);

最後に、ソートされた配列が表示されます。これを以下に示します。

printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";