WordPressやSymfonyのTipsを中心にアニメや日常の出来事について語ります。
メニュー

バブルソートの交換回数の問題を解いてみた!

この記事は約3分24秒で読めます

気泡がぶくぶく上昇中
ゆっきー
ども、カフェブロガーの悠木です。 お気に入りのカフェはドトールコーヒーです。 14時からの限定スイーツ「シューシャポー」が大好きです。

おもしろそうだったのでバブルソートの交換回数の問題を解いてみた!

CodeIQコード銀行 コードお預かり窓口さんからのウチに来ない?の問題

問題

バブルソートのアルゴリズムを用いて整数値のリストを昇順にソートする際、実際に数値の入れ替えを行う回数を高速に計算してください。

たとえば、
[5, 1, 4, 3, 2]
というリストなら、
[1, 5, 4, 3, 2]
[1, 4, 5, 3, 2]
[1, 4, 3, 5, 2]
[1, 4, 3, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 2, 4, 5]
[1, 2, 3, 4, 5]
のように、計7回数値の入れ替えを行うことになります。

入力・出力

整数値のリストが改行区切りで書かれたファイルが与えられます。
ファイルから数値を読み込んで、バブルソート時の『交換回数』を標準出力に出力してください。
上記の例なら、『7』と出力してください。

解答方法

まずはcount_bubble_sort.zipをダウンロードしてください。
中には8個のファイルが含まれています。

[01]answer.txt
解答用テキストファイルです。
必要事項を記入し、テキストファイルのままアップロードしてください。

[02]sample.in.txt
[03]sample.out.txt
例で示したデータと、その解答です。

[04]case01.in.txt
[05]case02.in.txt
[06]case03.in.txt
[07]case04.in.txt
[08]case05.in.txt
これを入力として、プログラムの実行結果を解答してください。

これ以降はネタバレ注意なので、
問題を自分で解こうという人はまだ見ないで下さい。

自分のプログラムコードを晒すのは恥ずかしいですが、
もっとこんな書き方あるんじゃない?などご指摘いただけるとうれしいです。

バブルソートとは

バブルとは「泡」のことで、
並べ替えの過程でデータが下から上へ移動する様子が、
泡が浮かんでいくように見えることからこの名前があります。

添え字 データ 1回 2回 3回 4回 5回 6回 7回
0 5 1 1 1 1 1 1 1
1 1 5 4 4 4 3 3 2
2 4 4 5 3 3 4 2 3
3 3 3 3 5 2 2 4 4
4 2 2 2 2 5 5 5 5

バブルソートの基本コード

上記の関数は配列を受け取り、バブルソートで並び替えた配列を返す関数です。

バブルソートの計算量(オーダー)

O(n2)

つまり、件数が2倍になったら4倍の時間がかかります。
ハッキリ言うと低速なソート方法です。

バブルソートについて分かりやすく解説されているサイトがあったので紹介します。

バブルソート(Bubble sort)|Oyster Harbor

プログラムコード

count_bubble_sort.zipをDドライブ直下に解凍して
D:\count_bubble_sort\count_bubble_sort.phpファイルを作成します。

私の場合はこんな感じに書きました。
もっといい書き方や分からない点などコメントいただけるとうれしいです。

コード自体は50行も行かなかったので、比較的コンパクトに書けたかなと思います。
1行にまとめれば短くはなりますが、見やすさを重視しました。

コード書いているときは気にしてなかったけど、
バブルソートって本当は後ろから要素を調べていくよね?

そもそもバブルソートってなんだっけ?から始まりましたからね。

大体の処理時間目安

  • バブルソートの調査 5分
  • バブルソートの処理 10分
  • ファイル読込み処理 10分
  • ファイルの出力処理 5分
  • 複数ファイル対応 5分
  • 計測ログの処理 5分

合計30分ということでなんとかお昼休み中に完成しました!
途中で気付いたのですが・・・。

ファイル名 件数 計算時間
case01.in.txt 10 件 0.02400 秒
case02.in.txt 100 件 0.00400 秒
case03.in.txt 10,000 件 22.35828 秒 [約 22.3 秒]
case04.in.txt 50,000 件 639.508588 秒 [約 10.7 分]
case05.in.txt 100,000 件 2574.04123 秒 [約 42.9 分]

10万件とか多すぎでしょ・・・!
どのくらい時間かかるか分からなかったので、計測ログを仕込んでみました。

case03 → case04 (30倍)
case04 → case05 (4倍)

なげぇ・・・!

作っている時間より動作確認する時間の方が長かった。

企業的にはJavaが1番需要あるようです。

・使用するプログラミング言語は問いません。
 が、以下の言語で書くと、企業からのスカウトがかかりやすくなります。
 ※企業のニーズが高い順です。企業のニーズ次第で並び順や言語の種類は変更になります。
 Java, Ruby, JavaScript, C++, PHP, C#, Python

Javaで書いた方が企業ウケがいいんでしょうな。
もう少ししたらRubyの環境をパソコンに作ろうと思ってたのでRubyで書き直してみようかな。

さいごに

久々にこういうプログラムを書きました。
なんか専門学生時代を思い出します。

こういうアルゴリズム考えるのっておもしろかったなぁ・・・。

追記:後ろから要素を比較するバブルソート

関数を差し替えればokです。
これで実行してみて、上に書いたコードと同じ結果が得られました。

ただ、こっちの方が多少処理が速かったです。

関連記事

  1. ペンとノート
  2. Gravator
  3. 【Sublime Text 3】ショートカットキー一覧(Windows/Mac対応)
  4. ホワイトボードを使ってプレゼンするホワイト企業の社員
  5. パソコン
  6. クエスタント

コメントをお待ちしております

PR

カテゴリー