Trouble Sort

Google Code Jam 2018 の予選、B問題の考察です。あくまで個人的な解法の紹介ですので、正確を期すためには、主催者の解説ページを参照してください。

問題

研究員がバブルソートならぬ「トラブルソート」という新しいアルゴリズムを考案しました。バブルソートでは2連続する要素同士を大小比較し、必要に応じて交換するという操作を繰り返しますが、トラブルソートでは3連続する要素の左端と右端を比較し、必要に応じて交換するという操作を繰り返します。ところがこのアルゴリズムには欠陥があります。整数の配列が与えられるので、それをトラブルソートで昇順に並べ替えようとしたとき、昇順にならない最初の箇所を指摘してください。

考察

今回はA問題よりも、このB問題のほうが簡単だったように感じましたが、バブルソートの知識がないと解きづらい問題だったかもしれません。

問題のカギ

文意から大小比較の様子を図に起こしてみると、次のようになります。


よく観察すると、奇数番目の要素群と偶数番目の要素群は互いにまったく干渉し合っていないことがわかります。つまり、1つの配列をトラブルソートすることは、2つの配列をそれぞれバブルソートしてミックスしているのと同じことです。

結論

実際に2つの配列を作り、それぞれソートした後に先頭から大小関係をチェックしていくことでこの問題は解けます。このときのソートはもちろんバブルソートである必要はありません。というよりも、ここでバブルソートを使ってしまうと、Small は解けても Large だと時間切れになるでしょう。標準ライブラリにあるソートを使えば、Large でも十分間に合います。

ソフトウェアの設計・実装がうまく行かなくてお困りではありませんか? 組込屋にお任せください。リモート案件は、常駐の半額でお受けしています。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)