1: 2019-03-31 (日) 17:09:32 njf |
2: 2019-03-31 (日) 18:01:40 njf |
| など。 | | など。 |
| | | |
- | *よくあるサンプルにはだまされないように [#x1b6384d] | + | *よくあるサンプルは使わないのが無難 [#x1b6384d] |
| | | |
| 「配列 ランダム 並び替え」などでインターネット検索すると次のようなコードを記載したページが上位に現れます。 | | 「配列 ランダム 並び替え」などでインターネット検索すると次のようなコードを記載したページが上位に現れます。 |
| randomList[j] = a | | randomList[j] = a |
| | | |
- | つまり、配列から順に要素を選び、次にランダムに配列を一つ選び、この二つを入れ替えていく物です。 | + | つまり、配列から順に要素を選び、次にランダムに要素を一つ選び、この二つを入れ替えていく物です。 |
| | | |
| これは結果がかなりかたよります。 | | これは結果がかなりかたよります。 |
| となり、明らかに14800ぐらいのものと、18500ぐらいのものに二分されました。 | | となり、明らかに14800ぐらいのものと、18500ぐらいのものに二分されました。 |
| | | |
- | これは[[こちら:http://nmi.jp/archives/541]]の記事で指摘されているように、アルゴリズムの構造的な欠陥です。 | + | これは[[こちらの記事:http://nmi.jp/archives/541]]で指摘されているように、アルゴリズムの構造的な欠陥です。 |
| | | |
- | たとえば3つのものの並べ替えの結果は3!=6通りですが、上のアルゴリズムでは3回3つの要素をランダムに入れ替えるので、3*3*3=27通りです。 | + | たとえば3つのものの並べ替えの結果は3!=6通りですが、上のアルゴリズムでは3回3つの要素をランダムに入れ替えるので、並び替えの方法の数は3*3*3=27通りです。 |
| | | |
- | 27は6で割り切れませんから、かならず上のアルゴリズムはそれぞれの結果に対して、どれかが多く、どれかが少ない並べ替えを行っています。(詳しくは[[上記記事:http://nmi.jp/archives/541]]にあります。) | + | 27は6で割り切れませんから、かならず上のアルゴリズムはそれぞれの結果に対して、どれかが多く、どれかが少なく並び替え方を割り振りを行って並べ替えています。(詳しくは[[上記記事:http://nmi.jp/archives/541]]にあります。) |
| | | |
| 今は長さ3の配列ですが、配列の長さが大きくなるにつれて不均等になりやすくなることも分かっています。 | | 今は長さ3の配列ですが、配列の長さが大きくなるにつれて不均等になりやすくなることも分かっています。 |