2021-ビーバーソート-解説
- 考案国：ドイツ
- 正解
- 「59～3600」
- 説明
- 60本の丸太を並び替えるためには、すべての丸太を調べるために、最低59回は動く必要があります。そこで、「0～30」と「6～70」は不正解であることがわかります。
- また、丸太が逆の順番になっていた場合は、すべての丸太を左端に移動していく必要があるため、「30本目の丸太であれば、丸太の場所に行くために28回右に移動して、丸太を左端に移すために28回左に移動する」必要があります。これを3本目の丸太から60本目の丸太まで繰り返して行う必要があるため、全部で「2(1+2+...+58)」回の移動が必要になり、計算すると3481回の移動が必要です。そこで、「59～300」も不正解であることがわかります。
- 実際のコンピュータでは
- データを小さい順や大きい順に並び替える処理は、整列（ソーティング）と呼ばれ、コンピュータの中で便利に活用されています。並べるデータは、数値であっても構いませんし、人名のような文字列であっても構いません。
- この問題では、ノームソートという2000年にイランのコンピュータ科学者が考案したアルゴリズムを扱いました。手順の考え方はシンプルで、「左端からデータを調べていき、大小順になっていないデータを見つけると、それを左のデータと比較しながら左端まで並べていく」処理を繰り返します。ソートされているデータに対しては、左端から調べていくだけなので早く処理が終わります。
- アルゴリズムの速さは、データ数が増えたときにどれくらい遅くなっていくかで比較します。ノームソートは、データ数の二乗で遅くなることが知られています。
注があるものを除き, このサイトの内容物は
