先頭へ戻る

単純ソート 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第1章

Programming Place Plus トップページ -- アルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① 降順にソートする単純ソートを作成してください。


本編のサンプルプログラムで使った simple_sort関数で、if文の不等号を変えるだけです。

/*
    単純ソート (降順)
*/
void simple_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t j = i + 1; j < size; ++j ){
            if( array[i] < array[j] ){
                SWAP(int, array[i], array[j]);
            }
        }
    }
}

問題②

問題② あなたの環境で、1000万個のデータを単純ソートでソートするとしたら、どれだけの時間が掛かりますか?


実際に、1000万個のデータを用意して試すことはできますが、途方もない時間が掛かることでしょう。

本編で試したように、管理者の環境では、

データ数 処理時間 (実測)
1000個 0.0015秒
10000個 0.265秒
100000個 21.59秒

という結果が出ています。O(n2) という計算量も踏まえて、データ数が 10倍になるごとに、処理時間は 100倍になると考えると、以下のようになると予想できます。

データ数 処理時間 (予測)
1000000個 約2000秒 = 約33分
10000000個 約200000秒 = 約2.3日

このように、1000万個のデータのソートには、丸2日は掛かります。

この結果は、あくまでも管理者の環境での予想値です。あなたの環境がもっと性能が良ければ、もう少しマシな結果になるかもしれませんが、逆にもっと悪い結果になるかもしれません。


参考リンク


------------------------------------------------------------------------

更新履歴

'2012/5/5 新規作成。



第1章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー