【C/C++】挿入ソートとバブルソート

アプリ開発方法ばかり勉強していましたが、アルゴリズムもやってみようかな思ったのでこちらの本を参考に書いてみました。

この本、4年前くらいに購入したのですが、アプリ開発ばかりやっていて全然使っていませんでした。久しぶりに読んでみましたが結構面白いですね。

とりあえずメモ書きとして残しておきます。

疑似乱数生成による初期化

とりあえず、入力データが必要なので用意します。毎回手入力するのが面倒臭いと思ったので、疑似乱数生成して自動で初期化しようと思いました。ライブラリ付属の rand() だけでは毎回同じデータが選ばれてしまうとのことなので、srand() で乱数を初期化します。オーソドックスなのはシステムクロック time() を使ったものらしいです。

10 で割ったあまりは 0 ~ 9 の間になるので、0~ 9 の範囲で値が欲しい時は 10 で剰余すればいいですね。

#include <iostream>
#include <random>
#include <time.h>

#define N 10 //データの数

using namespace std;

void input(int *data) {
    //疑似乱数初期化
    srand((unsigned int)time(NULL));
    
    for(int i = 0; i < N; i++)
        data[i] = rand() % 10;
}

挿入ソート

ソート済みとソートしていない領域で考えるそうです。要素を探していくとき、まさかデクリメントで遡ってさがすとは思いませんでした。最初、配列をコピーして上書きするようにして実装していましたが、途中で混乱したので解答例を参考にしました。

  1. 配列の要素の先頭から見ていったとき、ソートしてない要素をコピーしておく。
  2. その要素を基準に配列を遡って、適切な要素を見つける。
  3. 要素を1つずつずらしてから、そこに挿入する
#include <iostream>
#include <random>
#include <time.h>

#define N 10 //データの数

using namespace std;

void input(int *data) {
    //疑似乱数初期化
    srand((unsigned int)time(NULL));
    
    for(int i = 0; i < N; i++)
        data[i] = rand() % 10;

    cout << "入力データ : ";
    for(int i = 0; i < N; i++)
        cout << data[i] << " ";
    cout << endl;
}

void output(int *data) {
    cout << "ソートしたデータ : ";
    for(int i = 0; i < N; i++) 
        cout << data[i] << " ";
    cout << endl;
}

void insertionSort(int *data){
    int tmp; //一時保存用変数
    //要素を見ていく
    for(int i = 1; i < N; i++){
        int sort_element; //ソート済み要素数
        tmp = data[i]; //現在の要素を保持
        sort_element = i - 1; //現在の要素の1つ前まではソート済み
        /* ソート済み要素が 0 以上であり,
        ソート済み配列よりも現在の要素のほうが小さい場合*/
        while(sort_element >= 0 && tmp < data[sort_element]){
            //1つずらす
            data[sort_element + 1] = data[sort_element];
            //挿入箇所を遡って決める
            sort_element--;
        }
        //挿入する
        data[sort_element + 1] = tmp;
        output(data);
    }
}

int main(){
    //並べ替えるデータ
    int data[N];
    input(data);
    //挿入ソート
    insertionSort(data);
    
    return 0;
}

実行例

f:id:takunology:20200411101440p:plain

バブルソート

バブルと言われるだけあって、大きいデータ(泡)が上がっていくように並べる方法ですね。比較的実装しやすく、解答例を見なくてもできました。

  1. 配列の要素を順にみていき、その要素に注目
  2. 注目した要素の次の要素との大小関係を比較して入れ替える
  3. 最後の要素までいったとき、その要素はソート済みとする
  4. 1~3 を繰りかえす
#include <iostream>
#include <random>
#include <time.h>

#define N 10 //データの数

using namespace std;

void input(int *data) {
    //疑似乱数初期化
    srand((unsigned int)time(NULL));
    
    for(int i = 0; i < N; i++)
        data[i] = rand() % 10;

    cout << "入力データ : ";
    for(int i = 0; i < N; i++)
        cout << data[i] << " ";
    cout << endl;
}

void output(int *data) {
    cout << "ソートしたデータ : ";
    for(int i = 0; i < N; i++) 
        cout << data[i] << " ";
    cout << endl;
}

void swap(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void bubbleSort(int *data) {
    int sort_element = 0; //ソート済みの要素数
    while (sort_element != N - 1) {
        //1つずつ要素を隣に移動していく
        for(int i = 0; i < N; i++) {
            //次の要素と比較して大きい場合は入れ替える
            if(data[i] > data[i + 1]){
                swap(data[i], data[i + 1]);
                //入れ替え直後のデータ列
                //output(data);
            }
        }
        sort_element++; //ソート1回ごとにインクリメント
        output(data);
    }
}

int main(){
    int data[N];
    input(data);
    //バブルソート
    bubbleSort(data);
    
    return 0;
}

実行例

f:id:takunology:20200411102340p:plain

感想とか

正直、今のところ計算量は気にしていません。とりあえず実装できるようになりたいと思ったのと、内部的にどう動いているかを確認したかったのでやってみた感じです。あと、競技プログラミングって難しそうですね。

参考にしたサイト

ありがとうございます。

www9.plala.or.jp