第4回　Internet Explorerよりも速くソートできるかな

山下寛人
オイシックス株式会社

2008/11/5

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

- PR -

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

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

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

IE組み込みのソート

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

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

<html>

<head>

<script type="text/javascript">

Array.prototype.clone = function() {

  function f() {}

  f.prototype = Object(this);

  return new f();

}



Array.prototype.swap = function(i,j) {

  if(i == j) { return; }

  var tmp = this[i];

  this[i] = this[j];

  this[j] = tmp;

}



Array.prototype.toString = function() {

  var str = "";

  for(var i=0; i < this.length; i++) {

    if (i != 0) { str += ","; }

    str += this[i];

  }

  return "[" + str + "]";

}



Array.prototype.display = function(str) {

  if (this.view_id == undefined) { return; }

  if (str == undefined) { str = this.toString(); }

  var element = document.getElementById(this.view_id);

  element.innerHTML += str + "<br>";

}



function time(func, name, view_id) {

  var start = new Number(new Date());

  func();

  var end = new Number(new Date());

  var t = end - start;



  var element = document.getElementById(view_id);

  element.innerHTML += name + "の処理時間:" + t + "<br>";

}



function compare(a , b) {

  return (a - b);

}



//表示するための配列

var arrayForDisplay = new Array(10);

for(var i = 0; i<arrayForDisplay.length; i++) { arrayForDisplay[i] = i;}

arrayForDisplay.reverse();



//時間計測用の配列

var arrayForTime = new Array(700);

for (var i = 0; i < arrayForTime.length; i++) {

  arrayForTime[i] = Math.floor(Math.random() * arrayForTime.length);

}

</script> 

</head>

<body>



<span id="kumikomi"></span>

<script type="text/javascript">

var kumikomi = arrayForTime.clone();

var func = function() { kumikomi.sort(compare); }

time(func, "組み込みのソート", "kumikomi");

</script> 

<!-- 末尾1 -->

</body> 

</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」というコメントがある行の次の行に以下のソースを追加してください。

<hr/>

選択ソート<br/>

<span id="selection"></span>

<script type="text/javascript">

Array.prototype.getMinIdx = function(compare, l, r) {

  var min_idx = l;

  for (var i = l + 1; i < r; i++) {

    if (compare(this[i] , this[min_idx]) < 0) { min_idx = i; }

  }

  return min_idx;

}



Array.prototype.selectionSort = function(compare) {

  for (var i = 0; i < this.length-1; i++) {

    var min_idx = this.getMinIdx(compare, i, this.length);

    this.swap(i, min_idx);

    this.display();

  }

}

var selection = arrayForDisplay.clone();

selection.view_id = "selection";

selection.display();

selection.selectionSort(compare);

var selectionForTime = arrayForTime.clone();

func = function() { selectionForTime.selectionSort(compare); }

time(func, "選択ソート", "selection");

</script><!-- 末尾2 -->

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

3行目

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

5～11行目

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

13～19行目

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

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

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

1/3

Index
Internet Explorerよりも速くソートできるかな
	Page1 IE組み込みのソート選択ソート―最も単純なやり方
	Page2 バブルソート―泡が浮かび上がるように選択ソートとバブルソートのパフォーマンス
	Page3 シェルソート―グループごとに挿入ソートクイックソート―名は体を表す？クイックソートのパフォーマンス

コーディングに役立つ！アルゴリズムの基本

　Coding Edgeお勧め記事

	いまさらアルゴリズムを学ぶ意味コーディングに役立つ！アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
	Zope 3の魅力に迫る Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
	貧弱環境プログラミングのススメ柴田淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
	Haskellプログラミングの楽しみ方のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
	ちょっと変わったLisp入門 Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
	more

　　Coding Edgeフォーラム

フィード　 2.0／1.0／0.91

Coding Edge フォーラム新着記事

構造体の便利な用途、インターフェイス入門 （2010/3/10）
　継承機能を排除したインターフェイス機能でダックタイピングが可能となった。サンプルで確かめてみよう
プライベートモードの履歴状態 （2010/3/1）
　仕事に集中できるときと、なかなかできないとき、ありますよね。状態遷移図で考えてみよう
Goのswitch文で解くFizzBuzzと構造体のイントロ （2010/2/25）
　Goではif文と同等の制御構造をswitch文で表現できる。試してみよう
SQL4GでGAE＋Railsを体験しよう （2010/2/23）
　Google App Engine上でRDBMSを使ったRailsアプリケーションを構築する。環境設定手順を詳しく解説

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

RSSフィード

＠IT 新着記事

スキルアップ／キャリアアップ（JOB@IT）

Coding Edge

仮想環境の構築とデータ保護の特効薬？！
実績と信頼性の高いパッケージで安心運用
New！

仮想環境のバックアップもこれまでどおり
「まるごと取ってまるごと戻す」簡単運用

おばかアプリ選手権、第４弾開催中！！
ムダにカッコよくてくだらない作品求ム！

社内ファイルサーバを“クラウド”に統合
VPN直結「クラウド型ストレージ」を紹介

その数、なんと400台以上！グループ内
サーバの「統合管理」によるメリットは？

美人!? まあまあ？気になるいやし系!!
PV急増で「美人時計」がとった手段とは？

進化を続ける富士通ストレージETERNUS DX
製品開発者の自信を裏付けるものとは何か

運用管理の課題を“2つの観点”から分析
ユーザー満足度の高い「仮想環境」とは？

＠IT Special ヘ

ニュース一覧へ

お勧め求人情報

年収が落ち込んでいるのは自分だけ？
2万5000人から集めたデータをもとに、
現在のあなたの市場価値を判定

本気モードの企業がスカウト
人手不足を補う求人とはまったく違う、
優秀な人材だけが受け取れるスカウトメール

転職だって、縁とタイミングが重要
憧れの企業や職種へのキャリア・アップは、
まず「求人案件」との出会いから

JOB＠IT ヘ

ITトレメ「ビジネス基礎」シリーズ配信開始
「マナー＆コミュニケーション編」「法律・知財・債権管理編」

＊先週の人気講座ランキング＊
～Java編～

◆

上司や部下、部署内メンバーとの情報共有
を“ガラッ”と変えるコラボツールとは？
New！

◆

おばかアプリ選手権、第４弾開催中！！
ムダにカッコよくてくだらない作品求ム！

◆

社内ファイルサーバを“クラウド”に統合
VPN直結「クラウド型ストレージ」を紹介

◆

Twitterのアカウントはなぜ突破された？
メールによる新手の攻撃手法とその対策

◆

もう仮想化のお試しフェイズは終わりだ！
Hyper-V 2.0が基幹システムも仮想化

◆

美人!? まあまあ？気になるいやし系!!
PV急増で「美人時計」がとった手段とは？

◆

クライアント企業から求められる人材
⇒IT技術と経営戦略を併せ持つ「戦略家」

◆

.NET編集長が実践する「技術情報検索術」
サンプル・コードを簡単に探す“技”は？

◆

業務効率と情報セキュリティ対策を両立！
手間なく確実に機密情報を守る方法とは？

◆

直属上司が海外にいるのエンジニアに見る
【実例】場所に捉われないワークスタイル

◆

「仮想化工房」のマイスターが選んだのは
VMware、Hyper-V、そしてVirtageだった！

◆

進化を続ける富士通ストレージETERNUS DX
製品開発者の自信を裏付けるものとは何か

◆

運用管理の課題を“2つの観点”から分析
ユーザー満足度の高い「仮想環境」とは？

◆

【CTC事例】約30の基幹システムを統合！
膨大なバッジジョブを制御した方法は？

◆

仮想化すればコストは削減できるか？
仮想化に必要な「3つの視点」を解説する

◆

その数、なんと400台以上！グループ内
サーバの「統合管理」によるメリットは？

＠IT Special ヘ

＠ITトップ｜ Coding Edgeフォーラムトップ｜会議室｜利用規約｜プライバシーポリシー｜サイトマップ

Copyright(c) 2000-2010 ITmedia Inc.
著作権はアイティメディア株式会社またはその記事の筆者に属します。（著作権について）
当サイトに掲載されている記事や画像などの無断転載を禁止します。
「＠IT」「＠IT自分戦略研究所」「＠IT情報マネジメント」「JOB＠IT」「＠ITハイブックス」「＠IT MONOist」「ITmedia」「誠」「BARKS」は、アイティメディア株式会社の登録商標です。
当サイトに関するお問い合わせは「＠ITへのお問い合わせ」をご覧ください。

Index
Internet Explorerよりも速くソートできるかな
	Page1 IE組み込みのソート選択ソート―最も単純なやり方
	Page2 バブルソート―泡が浮かび上がるように選択ソートとバブルソートのパフォーマンス
	Page3 シェルソート―グループごとに挿入ソートクイックソート―名は体を表す？クイックソートのパフォーマンス

第4回 Internet Explorerよりも速くソートできるかな