並び替えのアルゴリズム

C++

http://www.geocities.jp/ky_webid/cpp/library/018.html

ソート以外で並び替えに関係するアルゴリズムの紹介です。

いくつか動作を確認してみます。

まずは要素を逆順に並び替えてくれるreverse関数を試してみます。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    vector<int> data;
    
    data.push_back(1);
    data.push_back(2);
    data.push_back(4);
    data.push_back(3);
    
    reverse(data.begin(),data.end());
    
    copy(data.begin(),data.end(),ostream_iterator<int>(cout,"\n"));
    
    return 0;
}

$ main
3
4
2
1

逆順になってますね。

お次は要素をランダムに入れ替えるrandom_shuffle関数を試してみます。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    vector<int> data;
    
    for(int i=0;i<10;++i) {
        data.push_back(i);
    }
    
    random_shuffle(data.begin(),data.end());
    
    copy(data.begin(),data.end(),ostream_iterator<int>(cout,"\n"));
    
    return 0;
}

$ main
8
1
9
2
0
5
7
3
4
6

バラバラに入れ替わっていますね。しかし実はこれだけだと問題があります。C言語のときに勉強しましたが、乱数表が同じなので何回実行しても同じ結果になってしまいます。

どこかで乱数の変更をしてやらなければなりません。

random_shuffleの第三引数に関数及び関数オブジェクトを指定してやることで可能となります。

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;

unsigned int random (unsigned int max) {
    srand( static_cast<unsigned int>( time(NULL) ) );
    return rand() % max;
}

int main () {
    vector<int> data;
    
    for(int i=0;i<10;++i) {
        data.push_back(i);
    }
    
    random_shuffle(data.begin(),data.end(),random);
    
    copy(data.begin(),data.end(),ostream_iterator<int>(cout,"\n"));
    
    return 0;
}

$ main
2
1
4
7
0
3
8
9
6
5

$ main
1
4
7
0
5
2
9
8
6
3

実行するたびに値が変わるようになりました。

ちなみに配列のシャッフルをするだけならC言語のときに自作しました。

配列のシャッフル - (void*)Pないと

しかし、listクラスとかでシャッフルって難しそうな気がします。また時間があればチャレンジしてみようかな。