単純ソート　解答ページ | 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万個のデータを用意して試すことはできますが、途方もない時間がかかることでしょう。

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

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

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

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

参考リンク 🔗

• Programming Place Plus　アルゴリズムとデータ構造編　参考書籍
  　– 当サイトの参考書籍一覧ページ。アルゴリズムとデータ構造に関する書籍を多数紹介。
• Programming Place Plus　アルゴリズムとデータ構造編　リンク集
  　– 当サイトの参考Webサイト集。アルゴリズムとデータ構造の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

• 2019/10/12
  • 全体的に見直して、大幅に修正
• 2019/9/2
  • 対応規格を C95 から C99 へ上げる
    • ループ制御変数を for文の初期設定式で宣言するように修正

’2012/5/5　新規作成。

第１章のメインページへ

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

Programming Place Plus のトップページへ