ソートアルゴリズムの原理とC言語実装

2024年11月13日 23:38

☆目的
出鱈目な順番に並んでいる数を順番に並べ替えること

☆各アルゴリズムの勉強方法
①【手元のカード】手順に従って順番に揃えて感覚的に理解する
②【プリントの表】手順に従って初期状態から表を埋める
③【プログラムの実装】テンプレートを使ってアルゴリズム部分のみを実装する

☆ソート(整列)の基礎知識
○整列はよく使う処理なので昔から様々なアルゴリズムが考案されている。
○昇順・・・小さい値から大きな値になるよう並び替えること
○降順・・・大きな値から小さい値になるよう並び替えること
○分類(比較するか？)
比較による整列(バブル・選択・挿入・クイック)は値の大小を比較してその結果によって並びを交換する手法。比較によらない整列(ビンソート・分布数え上げ・基数)は極めて高速だが数値の比較を行わないため常にこの手法が使えるとは限らない。

☆バブルソート
　データ列の隣り合う要素を比較し交換することを繰り返すことによりデータ列をソートする手法

① 隣り合う2つのデータを比較する
② もし順番通りになっていないのであれば入れ替える
③ さらに次のデータへ進み①と②を繰り返す
④ 1周終わったら同じことを最初のデータから繰り返す
⑤ データの数だけ周回したら終了する
※実装では入れ替えを逆からやってみます

以下のプログラムを実行してみる。バブルソート以降はアルゴリズム部分だけ置き換えて実行するのでこれがテンプレートとなる。

#include <stdio.h>
#include <stdlib.h>

/* 並べ替える数の生成パラメータ */
#define MAX 100
#define MIN 0
#define NUM_DATA 10
int dataArray[NUM_DATA];

/* ランダムな数字を生成させる関数 */
int getRandom(){
    return MIN + (int)(rand() * (MAX - MIN + 1.0) / (1.0 + RAND_MAX));
}

/* ソート対象のデータを表示 */
void ShowArray(int array[ ],int num){
    
    int i;

    for (i = 0; i < num ; i++){
        printf("%d\t", array[i]);
    }
    printf("\n");

}

  /* n個のデータの挿入ソートを行う関数 */
int BubSort(int array[ ], int num){
    
    int i, j, tmp;

    /* 配列の最初から最後まで繰り返す */
    for (i = 0; i < num - 1; i++) {
        
        /* 配列の最後から今現在の配列まで繰り返す */
        
        for (j = num - 1; j > i; j--) {
            
            /* もし前の要素の方が大きかったら交換する */
            if (array[j - 1] > array[j]) {
                tmp = array[j];
                array[j] = array[j - 1];
                array[j - 1]= tmp;
            }
            //ShowAarray(array, NUM_DATA);//ソートの途中経過を表示
        }
        
        //ShowAarray(array, NUM_DATA);//ソートの途中経過を表示
        
    }
}

int main(void){

    clock_t start = clock();
    
    /* ランダムな数字を生成させて配列に格納する */
    int i;
    for (i = 0; i < NUM_DATA; i++) {
        dataArray[i]=getRandom();
        //printf("%d,",dataArray[i]);
    }
    
    /* ソート前のデータを表示 */
    printf("ソート前:\n");
    ShowArray(dataArray, NUM_DATA);
    printf("\n\n");

    /* バブルソートを実行 */
    BubSort(dataArray, NUM_DATA);

    /* ソート後のデータを表示 */
    printf("\n\nソート後:\n");
    ShowArray(dataArray, NUM_DATA);
    
    /* 時間計測の処理 */
    clock_t end = clock();
    double time = (double)(end - start) / CLOCKS_PER_SEC;
    printf("\n\n");
    printf("実行時間は%fです。",time);
    
    return 0 ;
}

☆挿入ソート

手法の概要
① nつ目まで整列済みとする。nつ目とその右隣の数字を比較する
② もし右隣の数字の方が大きければ整列済みの配列の適切な場所へデータを挿入する
③ n+1つ目まで整列済みとする。これを繰り返す。

もっと具体的な手法
① nつ目まで整列済みとする。nつ目とその右隣の数字を比較する
② もし右隣の数字の方が大きければ、その数字を一時的な変数tmpに格納しておく
③ 整列済みの配列の最も右の数から順番に比較を繰り返していく
④ もしtmpより大きな数字だった場合は右にずらしていく
⑤ もしtmpより小さな数字だった場合はその右側にtmpの数を格納する
⑥ nつ目まで整列済みとして①の手順に戻る
⑦ 最後まで整列が終わったら終了する

  /* n個のデータの挿入ソートを行う関数 */
int InsSort(int array[ ], int num){
    
    int i, j, tmp;

    /* 整列済みの配列を全てにするまで繰り返す */
    for (i = 1; i < num; i++) {
        /* 未整列の中で最も左にある数字を一時的にtmpへ格納 */
        tmp = array[i];
        /* tmpより大きな数字を発見するまで数字を右にずらす */
        for (j = i; (j > 0 && array[j-1] > tmp) ; j--){
            array[j] = array[j-1]; 
        }
        /* 発見したtmpより大きな数字があった場所へtmpの数字を挿入する */
        array[j] = tmp;
        ShowArray(array,num);//ソートの途中経過を表示
        printf("左から%d番目の数字まではソートしてます\n\n",i);
    }
}

☆選択ソート

① 未整列の配列の中から最も小さい値を探す
② 整列済みの右側にある値と交換し整列済みとする
③ これを繰り返す

/* n個のデータの挿入ソートを行う関数 */
int SelSort(int array[ ], int num){
    
    int i, j, k, min, temp;

    for (i = 0; i < num - 1; i++) {
        
        //printf("%d番目の数である%dを暫定的最小値としました\n",i+1,array[i]);
        min = array[i];   // i番目の要素を暫定的最小値とする
        k = i;          // その添字を保存
        
        /* 暫定的最小値より後ろの数を順番に数えていく。*/
        /* 暫定的最小値より小さい値が現れたらその値を新しい暫定的最小値にする */
        for (j = i + 1; j < num ; j++) {
            if (array[j] < min) {       
                min = array[j];
                k = j;  // 新しい暫定的最小値が入っていた添字を保存しとく
            }
        }
        
        /* 古い暫定的最小値(i番目の要素)と新しい暫定的最小値の交換 */
        temp = array[i];  // 
        array[i] = array[k];
        array[k] = temp;
       
        //ShowArray(array, NUM_DATA);
        //printf("%d番目と%d番目の数を入れ替えました\n\n",i,k);
    }
}

☆ビンソート

数字を格納するビンを用意し、0から順番にラベルを付けておくイメージである。

/* ビンソートを行う */
void BinSort(int array[ ],int num){
    
    int i,j,max;
    
    /* 並び替えたい配列に入っている数字の中で最も大きい値をmaxとする。それを用意するビンの大きさとする。 */
    max=0;
    for (i = 0; i < num; i++){
        if(max<array[i]){
            max=array[i];
        }
    }
    
    int bin[max]; //ビンを作る

    /* ビンの中身を全て初期化しておく */
    for (i = 0; i <= max; i++){
        bin[i]=0;
    }

    /* 並び替えたい配列にある中身の数を一つ一つのビンのラベルに対応させて、その数字が幾つ存在するのか格納する */    
    for (i = 0; i < num; i++){
        bin[array[i]]=bin[array[i]]+1;
    }
    
    /* ビンの中身が0でないラベルの数を配列に格納し直す。 */
    j=0;
    for (i = 0; i <= max; i++){
        if(bin[i]!=0){
            //printf("%d\t",i);  //並び替えた配列を作らずに表示だけさせるならprintfする
            for(int k=1;k<=bin[i];k++){
                array[j]=i;
                j++;
            }
        }
    }

}

☆クイックソート

説明するのがめんどいので説明は省略する。

/* 配列の要素を交換する */
void Swap(int array[ ], int i, int j){
    int temp;
    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/* クイックソートを行う */
void QSort(int array[ ], int left, int right){
    
    int i, j;
    int pivot;

    i = left;                      /* ソートする配列の一番小さい要素の添字 */
    j = right;                     /* ソートする配列の一番大きい要素の添字 */

    pivot = array[(left + right) / 2]; /* 基準値を配列の中央付近にとる */
    //printf("%dをピポットとして整理しました\n",pivot);

    while (1) {                    /* 無限ループ */

        while (array[i] < pivot)       /* pivot より大きい値が */
            i++;                   /* 出るまで i を増加させる */

        while (pivot < array[j])       /* pivot より小さい値が */
            j--;                   /*  出るまで j を減少させる */
        if (i >= j)                /* i >= j なら */
            break;                 /* 無限ループから抜ける */

        Swap(array, i, j);             /* x[i] と x[j]を交換 */
        i++;                       /* 次のデータ */
        j--;
    }
    
    //ShowArray(array, NUM_DATA);               /* 途中経過を表示 */

    if (left < i - 1)              /* 基準値の左に 2 以上要素があれば */
        QSort(array, left, i - 1);     /* 左の配列を Q ソートする */
        //printf("左側：");
    if (j + 1 <  right)            /* 基準値の右に 2 以上要素があれば */
        QSort(array, j + 1, right);    /* 右の配列を Q ソートする */
        //printf("右側：");
}

☆実行時間を観測する

以下のプログラムはクロック数を記録することで実行時間を計算で導く単純なプログラムである。

以上の計算式で実行時間が分かるので、これをテンプレートとして各種ソートアルゴリズムの実行時間が分かるように改良すること。

#include <time.h>
#include <stdio.h>

int main(){

    clock_t start = clock(); //スタート時間取得
    
    /* ここに処理を入れる */
    
    clock_t end = clock(); //エンド時間取得
    
    double time = (double)(end - start) / CLOCKS_PER_SEC; //エンド時間からスタート時間を引き算
    
    printf("実行時間は%fです。",time);
    
    return 0 ;
    
}

☆並べ替える数を自動生成する
以下は乱数を用いてソートしたいデータを自動的に作成するプログラムである。これをテンプレートとして各種ソートアルゴリズムの実行時間が分かるように改良すること。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 並べ替える数に関する変数 */
#define MAX 10
#define MIN 0
#define NUM_DATA 100
int dataArray[NUM_DATA];

/* ランダムな数字を発生させる関数 */

int getRandom(){
    return MIN + (int)(rand() * (MAX - MIN + 1.0) / (1.0 + RAND_MAX));
}

int main(){
    
    /* 乱数のシードを時間で決定 */
    srand(time(NULL));
    
    /* ランダムな数を発生させて配列に格納する */
    
    int i;
    for ( i = 0 ; i < NUM_DATA ; i++ ){
        dataArray[i]=getRandom();
        printf("%d,",dataArray[i]);
    }
    
    return 0;
}

☆実行時間の比較

実験方法

① 条件を揃えた上でアルゴリズムごとの比較を行い表に記録する。
② 発生させる乱数の範囲を変えてみてそれぞれのアルゴリズム比較を行い表に記録する。
③ それぞれのソートアルゴリズムにおいて入れ替える数を増やすとどうなるか表に記録する。
※ クイックソートは配布されたものを使う。
※ 実行途中の表示を全て消すことで実行時の条件を揃えること。

結果の考察

ビン > クイック > 挿入 > 選択 > バブルの順番に性能が良かった。
バブルソートは効率的ではなく数値の入れ替え回数が無駄に多いと思われる。
クイックソート・挿入・選択はアルゴリズムを改良して効率を高めている。
ビンソートは数値の入れ替えや比較を行なっていないため実行速度が速いと思われる。