Internet Explorerよりも速くソートできるかな：コーディングに役立つ！ アルゴリズムの基本（4）（1/3 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

» 2008年11月05日 00時00分 公開
[山下寛人，オイシックス株式会社]

　ソートはアルゴリズムに関するテーマの中でも定番中の定番です。数値を数の大小で並べ替える。ただそれだけのことですが、ありとあらゆる手法があり、それぞれパフォーマンスやプログラムの分かりやすさなどに特徴があります。今回はさまざまなソートのアルゴリズムを紹介します。

　今日のプログラム言語の多くはソート機能を備えていて、自力でソートする機会はあまりありません。せっかく自力でソートするのですから組み込みのソートよりも高速にソートできるプログラムが作れるか、チャレンジしてみましょう。

　今回もWebブラウザ上のJavaScriptでプログラムを開発します。Internet Explorerに組み込まれているソートとのパフォーマンスを競ってみましょう。

IE組み込みのソート

　ソートのアルゴリズムを紹介する前に、JavaScriptの標準機能のソートでどれくらい時間がかかるか計測しましょう。また以後で共通に使用する関数も併せて作成します。

　本連載ではソースはコピー＆ペーストせず打ち込むことを推奨しておりますが、この部分はアルゴリズムそのものに関係ないのでコピー＆ペーストでも構わないでしょう。

  1. <html>
  2. <head>
  3. <script type="text/javascript">
  4. Array.prototype.clone = function() {
  5.   function f() {}
  6.   f.prototype = Object(this);
  7.   return new f();
  8. }
  9.  
  10. Array.prototype.swap = function(i,j) {
  11.   if(i == j) { return; }
  12.   var tmp = this[i];
  13.   this[i] = this[j];
  14.   this[j] = tmp;
  15. }
  16.  
  17. Array.prototype.toString = function() {
  18.   var str = "";
  19.   for(var i=0; i < this.length; i++) {
  20.     if (i != 0) { str += ","; }
  21.     str += this[i];
  22.   }
  23.   return "[" + str + "]";
  24. }
  25.  
  26. Array.prototype.display = function(str) {
  27.   if (this.view_id == undefined) { return; }
  28.   if (str == undefined) { str = this.toString(); }
  29.   var element = document.getElementById(this.view_id);
  30.   element.innerHTML += str + "<br>";
  31. }
  32.  
  33. function time(func, name, view_id) {
  34.   var start = new Number(new Date());
  35.   func();
  36.   var end = new Number(new Date());
  37.   var t = end - start;
  38.  
  39.   var element = document.getElementById(view_id);
  40.   element.innerHTML += name + "の処理時間:" + t + "<br>";
  41. }
  42.  
  43. function compare(a , b) {
  44.   return (a - b);
  45. }
  46.  
  47. //表示するための配列
  48. var arrayForDisplay = new Array(10);
  49. for(var i = 0; i<arrayForDisplay.length; i++) { arrayForDisplay[i] = i;}
  50. arrayForDisplay.reverse();
  51.  
  52. //時間計測用の配列
  53. var arrayForTime = new Array(700);
  54. for (var i = 0; i < arrayForTime.length; i++) {
  55.   arrayForTime[i] = Math.floor(Math.random() * arrayForTime.length);
  56. }
  57. </script> 
  58. </head>
  59. <body>
  60.  
  61. <span id="kumikomi"></span>
  62. <script type="text/javascript">
  63. var kumikomi = arrayForTime.clone();
  64. var func = function() { kumikomi.sort(compare); }
  65. time(func, "組み込みのソート", "kumikomi");
  66. </script> 
  67. <!-- 末尾1 -->
  68. </body> 
  69. </html>

　プログラムを解説します。

4～8行目

配列をコピーする関数です。

10～15行目

配列の中の2つの要素の値を交換する関数です。

17～24行目

配列の中身をカンマ区切りの文字列にする関数です。

26～31行目

配列の中身をWebブラウザに表示する関数です。

33～41行目

関数の実行時間を計測してWebブラウザに表示する関数です。

43～45行目

ソートする際にどういう順序でソートするかを決める関数です。ここでは数値の昇順になるようにしていますが、compare関数を変更することで降順にしたり文字列も含めたりしたソートにすることもできます。

47～56行目

配列を2種類作成します。

1つは分かりやすくするためにソートの途中経過を表示するための配列です。要素数が多いと画面に出しても訳が分からないので、要素数は10個です。最初は9から0まで降順にしてあります。

もう1つはパフォーマンス計測用です。要素数が少ないと一瞬で処理が終わって比較にならないので700個用意します。

61～66行目

ソートを実行してWebブラウザに実行時間を表示します。

　それでは実行してみてください。実行はいつもどおりソースをHTMLファイルとして保存してWebブラウザで開いてください。IEで警告が出た場合は実行を許可するようにしてください。

　筆者のPCでは60前後でした。配列は乱数で作成しているので実行するたびに多少時間は前後する場合があります。これが今回の目標値になります。果たしてこれより速くできるのでしょうか。

　なお、PCの性能によって時間がかかり過ぎたり、早く終わったりする場合があるかと思います。53行目のnew Array()の中の数を変更することで調整できますので、実行時間が60前後になるように調整するとよいでしょう。

選択ソート―最も単純なやり方

　選択ソートは最も単純なソートのアルゴリズムの1つです。

　一番小さい値を全体の中から選びます。それを配列の最初に格納します。次に残ったものの中から同じように一番小さい値を選び、配列の2番目に格納します。これを最後まで繰り返します。

　先ほどのソースの67行目、「末尾1」というコメントがある行の次の行に以下のソースを追加してください。

  1. <hr/>
  2. 選択ソート<br/>
  3. <span id="selection"></span>
  4. <script type="text/javascript">
  5. Array.prototype.getMinIdx = function(compare, l, r) {
  6.   var min_idx = l;
  7.   for (var i = l + 1; i < r; i++) {
  8.     if (compare(this[i] , this[min_idx]) < 0) { min_idx = i; }
  9.   }
  10.   return min_idx;
  11. }
  12.  
  13. Array.prototype.selectionSort = function(compare) {
  14.   for (var i = 0; i < this.length-1; i++) {
  15.     var min_idx = this.getMinIdx(compare, i, this.length);
  16.     this.swap(i, min_idx);
  17.     this.display();
  18.   }
  19. }
  20. var selection = arrayForDisplay.clone();
  21. selection.view_id = "selection";
  22. selection.display();
  23. selection.selectionSort(compare);
  24. var selectionForTime = arrayForTime.clone();
  25. func = function() { selectionForTime.selectionSort(compare); }
  26. time(func, "選択ソート", "selection");
  27. </script><!-- 末尾2 -->

　プログラムを解説します。

3行目

この位置にプログラムの出力結果を表示します。

5～11行目

配列の中の最小の値を持つインデックスを調べて返す関数です。インデックスがlとrの間の範囲を調べます。

13～19行目

選択ソートです。元の配列と出来上がりの配列を同じにして、配列の0番目から最小の値と入れ替えるようにしています。

　では実行してみましょう。結果はいかがだったでしょうか。

　残念ながら全く勝負にならなかったと思います。こんな単純なやり方で勝てるほど世の中甘くはありません。

　　　　　　 1|2|3 次のページへ

Copyright © ITmedia, Inc. All Rights Reserved.

スポンサーからのお知らせPR

Coding Edge 記事ランキング

本日月間

注目のテーマ

4AI by ＠IT - AIを作り、動かし、守り、生かす
Microsoft ＆ Windows最前線2025
AI for エンジニアリング
ローコード／ノーコード セントラル by ＠IT - ITエンジニアがビジネスの中心で活躍する組織へ
Cloud Native Central by ＠IT - スケーラブルな能力を組織に
システム開発ノウハウ 【発注ナビ】PR
あなたにおすすめの記事PR

@ITについて

RSSについて

アイティメディアIDについて

メールマガジン登録

＠ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。