整列アルゴリズムを比較する(交換法編)

どうも、じゃがいもよりのポテト君です(?)

前回は準備編をしました。

ということで、今回は1つ目の基本交換法(バブルソート)を作っていきます。

まずは、交換法の説明をしていきます。

交換法とは、最初の要素から順に隣り合う要素を比較して、スワッピング(中身を交換すること)を繰り返していく整列アルゴリズムです。
例えば
{5,8,2,1}を昇順に交換法で整列するときは
(まずは5,8,2,1を順に比較します。)
1. 5>8ではないからそのまま{5,8,2,1}
2. 8>2なので{5,2,8,1}
3. 8>1なので{5,2,1,8}
(1周した3.の時点で最後の要素が決まるので、2周目は残りの5,2,1を比較します。)
4. 5>2なので{2,5,1,8}
5. 5>1なので{2,1,5,8}
(残りの2,1を比較します。)
6. 2>1なので{1,2,5,8}
このように大きな値が泡のように後ろへ上がってくるため、バブルソートというらしいです。

因みに計算量はO(n^2)です。
それより大事な情報として比較回数はn(n-1)/2回です。

交換法のアルゴリズムを説明したので、これをC++プログラムに書き換えます。
今回は、整列を行う関数を"sort.hpp"というファイル名のヘッダファイル(インポートをして他のプログラムで使うためのファイル)を作って記述していきます。(他の整列アルゴリズムも同じファイルに記述していきます。)

関数は引数として
整列を行うint型配列(参照渡し) , 配列の長さ
を渡すようにします。
参照渡しということは、関数内で配列に変更を行った場合渡した元々の配列に変更が行われるということです。(そもそもC++では配列の値渡しは疑似的にしか行えません。)
C++では、配列をそのまま渡すことはできず、先頭要素を示すポインタとして渡されます。(C系言語を使ったことがない人にはわかりずらいかもしれません)
また、ポインタとして渡された配列から、要素数を求めるのは難しい(そもそも可能なのだろうか)ので、先に配列の時点で要素数を求めてもらうことにします。
因みに、配列の要素数は
sizeof 配列名 / sizeof 配列名[0]
で求められます。
配列全体のビット数 / 配列の0個目の要素のビット数という意味です。

//sort.hpp
#ifndef SORT
#define SORT
void bubble(int array[],int array_size){
    int sw;
    for(int i=array_size;i>1;i--){
        for(int j=0;j<i;j++){
            if(array[j]>array[j+1]){
                sw=array[j];
                array[j]=array[j+1];
                array[j+1]=sw;
            }
        }
    }
}
#endif

短いので今回は番号付きリストにはしてません。(やっぱりソースコードっていうとこっちの方が見た目が合うんですよねぇ)

説明…これ以上要りますか?((((((
少しだけ説明しますね。
1つ目のfor文でのiは、比較回数の制限として使用します。
入れ子のfor文では順に比較をしています。
スワッピングのやり方ですが、変数a,b間で行うとした場合別の変数sを用意します。
sにaを一時的に保存してから、aにbを代入します。その後にbにsを代入します。
sがないと、a,bが両方とも同じ値になってしまいます。

ということで、これで交換法の整列プログラムが完成しました!
試しに下のソースコードを実行してみると

import "sort.hpp"
import <iostream>
using namespace std;
int a[] = {7,3,9,1,6,2,4,5,8,0} ,size;
size = sizeof a / sizeof a[0];
bubble(a ,size);
for(int i=0;i<size;i++){
    cout<<a[i]<<",";
}

結果は
0,1,2,3,4,5,6,7,8,9
となるはずです。

実行時間の計測は一通り作成した後にします。
ということでまた次回!
次回は選択法です!