【C言語】ヒープソートによる配列データの整列

ある程度プログラミングに慣れた人向けの練習問題の一つとして、整列アルゴリズム（ソート）の実装があります。

この記事では、ヒープソートを用いた配列データの整列をプログラムに実装する方法について解説しています。

ヒープソートの概要

プログラムを作成する前に、ヒープソートについての簡単な説明を行います。

ヒープソートとは、配列データの要素を整列させる整列アルゴリズム（ソート）の一つです。

アルゴリズム

ヒープソートでは、「整列対象となる配列をヒープ（完全2分木）に対応付ける」という操作を行います。

根の部分にはそのヒープの中で最大（もしくは最小）の値となる要素が格納されます。

この要素を取り出し、残りの要素でヒープを再構築するという流れを繰り返すことで配列データの整列を行います。

計算量

ヒープソートはどのような配列データに対しても計算量はO記法でO(NlogN)です。

計算量が配列データに依存しない安定した整列アルゴリズムとして知られています。

実際にプログラムを作成してみる

前述のアルゴリズムに従ってプログラムを作成します。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。使用する言語はC言語です。

#include <stdio.h>

void swap(int data[], int a, int b){
  int temp;
  temp = data[a];
  data[a] = data[b];
  data[b] = temp;
}

void down_heap(int data[], int root, int leaf){
  int i, temp;
  temp = data[root];
  i = root * 2 + 1;
  if(i+1<=leaf && data[i]<data[i+1]){
    i = i + 1;
  }
  while(i<=leaf && temp<data[i]){
    data[root] = data[i];
    root = i;
    i = root * 2 + 1;
    if(i+1<=leaf && data[i]<data[i+1]){
      i = i + 1;
    }
  }
  data[root] = temp;
}

void heap_sort(int data[], int n){
  int i, cur, w;
  cur = 1;
  while(cur <= n){
    w = cur;
    while(w>0 && data[w/2]<data[w]){
      swap(data, w, w/2);
      w = w / 2;
    }
    cur = cur + 1;
  }

  i = n - 1;
  while(i > 0){
    swap(data, 0, i);
    i = i - 1;
    down_heap(data, 0, i);
  }
}

int main(void){

  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n;

  /* 整列前のデータを表示する */
  printf("---heap sort---\nBefore : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  /* ヒープソートを用いてデータを整列する */
  heap_sort(data, n);

  /* 整列後のデータを表示する */
  printf("\nAfter  : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

---heap sort---
Before : 9 8 7 6 5 4 3 2 1 
After  : 1 2 3 4 5 6 7 8 9 

この出力結果から無事にヒープソートが実装できていることがわかります。

おすすめの記事

本記事を読まれた方には、以下の記事もおすすめします。

【中・上級者への道！】C言語の次に勉強するべきプログラミング言語は何？【オススメは○○】