C++ での選択ソートによる動的配列

はじめに

この実験では、選択ソートアルゴリズムを使ってC++ で未ソートの動的配列をソートするための選択ソートの実行方法を学びます。

Skills Graph

新しいC++ ファイルを作成する

まず、~/project ディレクトリに main.cpp という名前の新しいC++ ファイルを作成します。

touch ~/project/main.cpp

選択ソートアルゴリズムを実装する

選択ソートアルゴリズムは、最小要素を選択して配列の先頭に配置し、次に配列の残りから次の最小要素を選択してインデックス1に配置し、これを繰り返して配列が完全にソートされるまで行います。以下は、C++ で選択ソートアルゴリズムを実装する方法です。

#include <iostream>
using namespace std;

// 2つの要素の位置を交換する関数
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// 選択ソートアルゴリズムを実行する関数
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // 降順にソートするには、この行の > を < に変更します。
      // 各ループで最小要素を選択します。
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // 最小値を正しい位置に配置します
    swap(&array[min_idx], &array[step]);
  }
}

このコードブロックでは、配列内の2つの要素の位置を交換する関数 swap() と、配列に対して選択ソートアルゴリズムを実行する関数 selectionSort() を定義しています。

配列を入力する

このステップでは、ソートする必要のある動的配列を入力します。これは、ユーザーに配列の要素を1つずつ入力するように促すことで行うことができます。

// ドライバーコード
int main() {
  int size;
  cout<<"Enter the size of the array: ";
  cin>>size; //配列のサイズを入力する
  int* data = new int[size]; //動的に配列を宣言する

  // 配列の要素を1つずつ入力する
  for(int i = 0; i < size; i++) {
    cout<<"Enter element "<<i+1<<" : ";
    cin>>data[i];
  }

選択ソートを実行する

これで未ソートの配列があるので、先ほど定義した selectionSort() 関数を使ってその配列に対して選択ソートアルゴリズムを実行できます。方法は以下の通りです。

  // 選択ソートを実行する
  selectionSort(data, size);

ソート済み配列を出力する

最後に、printArray() と呼ばれる関数内でループを使ってソート済み配列をコンソールに出力します。方法は以下の通りです。

  // ソート済み配列を出力する
  cout << "\nSorted array: ";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // 動的配列によって使用されるメモリを解放する
  delete[] data;
  return 0;
}

コードをコンパイルして実行する

コードをコンパイルして実行するには、ターミナルを開き、main.cpp ファイルが保存されているフォルダに移動します。その後、次のコマンドを実行します。

g++ main.cpp -o main
./main

ソート済み配列がコンソールに表示されるはずです。

まとめ

この実験では、C++ で未ソートの動的配列をソートするために選択ソートアルゴリズムをどのように使用するかを学びました。そのために、配列を入力し、選択ソートアルゴリズムを実装し、ソートを実行し、ソート済み配列を出力し、そしてターミナルでコードをコンパイルして実行する必要がありました。これらのスキルを使えば、選択ソートを使って任意のサイズの配列をソートすることができます。