2012.01.19ソートのアルゴリズムについて調べました。代表的なソート方法5種類について概略をまとめます。n個の要素を持つ配列を昇順(小さい数から大きい数)にソートする場合です。バブルソート1番目の要素と2番目の要素を比較。大小が逆ならば要素を入れ替える。続いて1番目と3番目を比較。これを1番目とn番目まで繰り返すと最初の要素が最小になる。次に2番目と3番目を比較、2番目と4番目を比較、2番目とn番目を比較。これを繰り返すと2番目の要素が2番目に小さい数となる。これをn-1番目とn番目の比較まで繰り返す。挿入ソート2番目の要素と1番目の要素を比較。大小が逆ならば要素を入れ替える。次に3番目と2番目を比較。大小が逆ならば要素を入れ替える。逆でなければ3番目と1番目を比較。大小が逆ならば3番目を1番目の要素に入れ、1番目を2番目、2番目を3番目に順次入れる。これをn番目とn-1番目の比較まで繰り返す。選択ソートn個の要素を片端から全て調べ最小の要素を取り除く。この要素を別の配列の1番目の要素に入れる。元の配列の要素はn-1個になる。残ったn-1個の要素を全て調べ最小の要素を取り除く。この要素を別の配列の2番目の要素に入れる。元の配列の要素はn-2個になる。マージソート配列の要素が1個の場合はその配列を返す。配列の要素が2個以上の場合は配列を前半と後半に2等分する(奇数の場合は中央の要素をどちらかに含める)。前半の配列をマージソートする。後半の配列をマージソートする。前半と後半の配列をマージする。※配列のマージを参照。クイックソート配列の要素が1個の場合はその配列を返す。配列の要素が2個以上の場合は最後の要素を取り除き、この要素を「ピボット」として記憶しておく。別の配列を二つ用意する。全ての要素をピボットと比較し、小さければ前半の配列に順次入れる。なければ後半の配列に順次入れる。前半の配列をクイックソートする。後半の配列をクイックソートする。前半の配列、ピボット、後半の配列の順でつなげる。マージソートとクイックソートは「再帰」という手法を使うので分かりにくいかもしれません。どのアルゴリズムも結果は同じになりますので、ポイントはスピードです。1000個のランダムな数をソートした場合にかかる時間についてまとめました。コードはJavaScriptで書きました。20バブルソートを100として比較しています。数値が少ないほど速いです。遅いと言われているのがバブルソートで、速いと言われているのがクイックソート。その通りの結果になりました。予想外なのはマージソートの遅さです。私のコーディングがまずいのかもしれません。コピーstabuckyをフォローするstabucky関連記事JavaScriptJavaScriptの意外な挙動プログラムを書いているとよくエラーが起きます。エラーが起きないように修正していくことでプログラムが完成します。困るのはエラーが起きないのに意図通りに動かない場合です。これは原因を探るのが難しいです。困るのは「このように動くはずだ...JavaScriptjQueryを使いクリックする代わりにEnterキーを押すHTMLのformにあるsubmitボタンはEnterキーを押すとクリックしたことになるのですが、JavaScriptで制御している場合はEnterキーが効きません。jQueryを使ってEnterキーを押すとボタンをクリックしたことになる...JavaScriptJavaScript、二次元配列でソートJavaScriptで、二次元配列を任意の列でソートする方法です。数値でソートするものとし、昇順、降順が指定できます。JavaScriptJavaScriptで日付をコピーする方法JavaScriptで日付オブジェクトをコピーする際、単に代入するだけだと予期しないことが起きます。JavaScriptピボットテーブルを表示するjQueryプラグインExcelにはピボットテーブルという機能があります。クロス集計と呼ぶ人もいます。これをHTMLのテーブルで再現するjQueryプラグイン「jquery.pivot.js」を作りました。JavaScript長音を含む文字列を辞書順でソート辞書の言葉の並び順はアイウエオ順ですが、「ー」という伸ばす音、長音があるときは、その前の音によって判断されます。その前の音がア段ならば「ア」、イ段ならば「イ」となります。「ワード」ならば「ワアド」、「キー」ならば「キイ」として並び...罫線の下端で改ページするマクロおかしなうまい棒スティックパーティーコメントコメントを書き込むコメントをどうぞメールアドレスが公開されることはありません。曖昧な記憶と憶測でロックを語る最後は運です。Cool.ホーム検索トップサイドバータイトルとURLをコピーしました。