配列内のデータをソートする(分布数え/計数ソート)


動作ブラウザ 【 IE:3.0  NN:2.0
Internet Explorer Netscape Navigator DreamPassport iCab
3.0x 4.0x 4.5 5.0x 5.5 2.0x 3.0x 4.0x 4.x 6.0 2 3 2.x
Windows - - -
Macintosh - - -
UNIX - - - - - - - -
Dreamcast - - - - - - - - - - -

ポイント count = new Array(); buff = new Array(); for (i=0; i<=max-min; i++) count[i] = 0; for (i=0; i<data.length; i++) count[data[i] - min]++; for (i=1; i<=max-min; i++) count[i] += count[i-1]; for (i=data.length-1; i>=0; i--) { n = data[i]-min; buff[--count[n]] = n; } data = buff;
説  明 ソート方法の1つに分布数え/計数ソートがあります。データの値の度数分布を求め累積し、順位に変換し、最後に順位の場所にデータを入れ直すことでソートが行われます。
サンプル <html> <head> <title>配列内のデータをソートする(分布数え/計数ソート)</title> <script language="JavaScript"><!-- data = new Array(30,10,5,99,44,65,10,31,1,57,88,78); max = 100; min = 0; function sortData(start,end) { count = new Array(); buff = new Array(); for (i=0; i<=max-min; i++) count[i] = 0; for (i=0; i<data.length; i++) count[data[i] - min]++; for (i=1; i<=max-min; i++) count[i] += count[i-1]; for (i=data.length-1; i>=0; i--) { n = data[i]-min; buff[--count[n]] = n; } data = buff; } function printArray() { for (i=0; i<data.length; i++) document.write(data[i],", "); document.write("<br>"); } // --></script> </head> <body> 配列内のデータをソートする(分布数え/計数ソート)<br><br> ソート前:<br> <script langauge="JavaScript"><!-- printArray(); // --></script> <br> ソート後:(昇順)<br> <script langauge="JavaScript"><!-- sortData(0,data.length-1); printArray(); // --></script> </body> </html>
補足説明 参考:C言語による最新アルゴリズム辞典 奥村晴彦著。ISBN4-87408-414-1

■サンプルスクリプトを実行する >>実行
■各ブラウザでの動作結果を見る >>View!

写真素材 PIXTA