動的配列で挿入ソートをマスターする

はじめに

この実験では、C++ の動的配列を使って挿入ソートアルゴリズムを実装する方法を学びます。このアルゴリズムは、単純なソートアルゴリズムで、リストをソート済みと未ソートの 2 つの部分に分割し、その後、未ソートのリストの各要素をソート済みのリストの適切な位置に挿入することで動作します。

動的配列の作成

まず、ユーザーによって決定されるサイズの整数型の動的配列を作成し、1 から 100 までの乱数で埋めます。

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Enter the size of the array: ";
    cin >> size;

    // 動的配列を作成
    arr = new int[size];

    // 配列を 1 から 100 までの乱数で埋める
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

未ソートの配列を表示する

次に、未ソートの配列の内容をユーザーに表示します。

    // 未ソートの配列を表示
    cout << "Unsorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

挿入ソートアルゴリズムの実装

次に、昇順に配列をソートする挿入ソートアルゴリズムを実装します。

    // 挿入ソート
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

ソート済みの配列を表示する

ソート済みの配列の内容をユーザーに表示します。

    // ソート済みの配列を表示
    cout << "Sorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

メモリの解放

最後に、動的配列によって使用されるメモリを解放します。

    // メモリを解放
    delete [] arr;

    return 0;
}

プログラムをコンパイルして実行する

ファイルを ~/project ディレクトリに「sort.cpp」として保存します。

ターミナルでプログラムをコンパイルして実行します：

$ cd ~/project
$ g++ sort.cpp -o sort
$./sort

まとめ

この実験では、C++ で動的配列を使って挿入ソートアルゴリズムを実装する方法を学びました。ユーザーによって決定されるサイズの動的配列を作成し、それにランダムな整数を格納し、挿入ソートアルゴリズムを実装し、最後にソート済みの配列をユーザーに表示しました。また、動的配列によって使用されるメモリを解放する方法も学びました。

動的配列を用いた挿入ソート