【C言語】選択法（又は選択ソート）による配列データの整列

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

この記事では、選択法（選択ソートとも呼ばれる）を用いた配列データの整列をプログラムに実装する方法について解説しています。

選択法（選択ソート）の概要

プログラムを実装する前に、選択法（又は選択ソート）についての簡単な説明を行います。

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

アルゴリズム

選択法（選択ソート）では、整列対象の配列に存在する要素の中から最小のものを選択し、配列先頭の要素と位置を入れ替えるという操作を行います。

位置が入れ替えられ、配列の先頭に配置された要素は整列対象の範囲から外されるため、上記の操作を何度も繰り返すことで徐々に配列内の要素が整列されていく仕組みです。

計算量

長さNの配列が対象の場合、選択法では長さN、N-1、N-2…の各配列断片から最小値となる要素を見つけるため、それぞれN-1、N-2、N-3…回の比較が行われます。

比較を行う回数の合計は(N(N-1)/2)回であり、O記法での計算量はO(N^2)となります。

選択法（選択ソート）はメジャーではありますが、残念ながら決して効率の良いアルゴリズムではありません。

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

早速ですが、実際にプログラムを作成していきます。

プログラム作成の手順

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

実装例

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

#include <stdio.h>

int main(void){
  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n, i, j, min, temp;

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

  /* 選択法（選択ソート）を用いてデータを整列する */
  i = 0;
  while(i < n){
    min = i;
    for(j=i+1; j<n; j++){
      if(data[j]<data[min]){
        min = j;
      }
    }
    temp = data[i];
    data[i] = data[min];
    data[min] = temp;
    i += 1;
  }

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

  return 0;
}

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

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

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

おすすめの記事

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

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