CodeIQ MAGAZINECodeIQ MAGAZINE

クイックソートとバブルソートを比較してみよう #PHP

2014.05.02 Category:技術コラム Tag:

  • 7
  • このエントリーをはてなブックマークに追加

プログラミングでは、データを並べ替えて整列する、という処理(ソート)を行う事があります。もちろん、PHPでもその機能があります。ビルトインでsort()関数が用意されています。

普段のプログラミングでは、このsort()関数を使えば良いのですが、今回は、少し寄り道して、ソートそのものの処理について考えてみましょう。
by レスキューワーク株式会社 水野史土

クイックソートとバブルソート

ソートの方法には様々な方法があります。よく知られているものには、クイックソートやバブルソートなどがあります。ほかにもソート方法がありますが、ここではこの2つを紹介します。尚、今回は要素の値は全て異なる前提とします。

バブルソート

バブルソートは、一番小さい(or大きい)ものを端に移動する、という処理を繰り返し行うことで、最終的に整列させる方法です。以下のような手順で行います。

(1) 配列の、隣り合う要素の大小比較を行い、小さければ入れ替える、という処理を行います。

(2) 操作(1)を先頭(左)から順に行っていくと、最後の要素が最小になります。

(3) 一番最後の要素を除いた残りの要素について、再び大小比較を行います。

(4) これを繰り返すと、大->小(先頭->末尾)の順に並びます。

$data = array(3,12,8,5,2,13,4,9,15,1,10,0,11,6,7,14);
$len = count($data);
$step = 0;
bsort($data,$len);
echo $step;
echo ': ';
echo implode(', ',$data);
echo PHP_EOL;
function stepcounter() {
    global $data;
    global $step;
    $step++;
    if (($step % 10) == 0) {
        echo $step;
        echo ': ';
        echo implode(', ',$data);
        echo PHP_EOL;
    }
}
function bsort(&$array,$length) {
    // 長さが1なら抜ける
    if ($length <= 1) {
        return;
    }   
    for ($position = 0; $position < $length; $position++) {
        // 左から順に、隣と比べる。左が小さければ入れ替える
        if ($array[$position] < $array[$position+1]) {
            $tmpdata = $array[$position];
            $array[$position] = $array[$position+1];
            $array[$position+1] = $tmpdata;
        }
        stepcounter();
    }
    // 一番最後を除いて、ソート処理を実行する
    bsort(&$array,$length-1);
}

クイックソート

クイックソートは、基準値(ピボット)を定め、この値より大きいものを左に移動する、小さいものを右に移動する、という処理を繰り返し行うことで、最終的に整列させる方法です。以下のような手順で行います。

(1) 基準値(ピボット)を選びます。サンプルコードでは並びの真ん中を選択しています。

(2) 配列の先頭(左)から、ピボットより小さいものを探します。配列の末尾(右)から、ピボットより大きいものを探します。

(3) 「ピボットより小さいもの」と、「ピボットより大きいもの」を入れ替えます。

(4) 先頭から探していくのと末尾から探していくのを続けると、どこかで同じ要素のところに来ます。そうしたらこのサ
イクルは終わりです。

(5) こうすると配列の先頭寄りはピボット以下の数、配列の末尾寄りはピボット以上の数、となります。

(6) (4)の同じ要素のところで、配列を分割します。分割した配列それぞれに処理を繰り返します。

$data = array(3,12,8,5,2,13,4,9,15,1,10,0,11,6,7,14);
$len = count($data);
$step = 0;
qsort($data,0,$len-1);
echo $step;
echo ': ';
echo implode(', ',$data);
echo PHP_EOL;
function stepcounter() {
    global $data;
    global $step;
    $step++;
    if (($step % 10) == 0) {
        echo $step;
        echo ': ';
        echo implode(', ',$data);
        echo PHP_EOL;
    }
}
function qsort(&$array,$start,$end) {
    // 長さが1なら抜ける
    if ($start >= $end) {
        return;
    }
    // ピボットの設定。ここでは並びの真ん中を選択した
    $mid = (int) ($start+$end)/2;
    $pivot = $array[$mid];
    // 両端の位置を設定。
    $left = $start;
    $right = $end;   
    while ($left <= $right) {
        // 左から、ピボットより小さいものを探す
        while ($pivot  $array[$right]) {
            $right--;
            stepcounter();
        }
        if ($left <= $right) {
            // 要素を交換する
            $tmpdata = $array[$left];
            $array[$left] = $array[$right];
            $array[$right] = $tmpdata;

            // 交換したら、次の要素へ移る
            $left++;
            $right--;
            stepcounter();
        }
    }
    // 分割した部分ごとに、ソート処理を実行する
    qsort($array,$start,$right);
    qsort($array,$left,$end);
}

ステップ数

実際にarray(3,12,8,5,2,13,4,9,15,1,10,0,11,6,7,14)をソートしてみました。結果は下記の通りです。一番左は処理ステップ数です。

クイックソート

10: 14, 12, 11, 10, 15, 13, 4, 9, 2, 1, 5, 0, 8, 6, 7, 3
20: 14, 12, 15, 13, 11, 10, 9, 4, 2, 1, 5, 0, 8, 6, 7, 3
30: 15, 14, 13, 12, 11, 10, 9, 4, 2, 1, 5, 0, 8, 6, 7, 3
40: 15, 14, 13, 12, 11, 10, 9, 7, 6, 8, 5, 3, 1, 2, 4, 0
50: 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
52: 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

バブルソート

10: 12, 8, 5, 3, 13, 4, 9, 15, 2, 10, 1, 0, 11, 6, 7, 14
20: 12, 8, 5, 13, 3, 4, 9, 15, 2, 10, 1, 11, 6, 7, 14, 0
30: 12, 8, 5, 13, 4, 9, 15, 3, 10, 2, 11, 6, 7, 14, 1, 0
40: 12, 8, 13, 5, 9, 15, 4, 10, 3, 2, 11, 6, 7, 14, 1, 0
50: 12, 13, 8, 9, 15, 5, 4, 10, 3, 11, 6, 7, 14, 2, 1, 0
60: 13, 12, 8, 9, 15, 5, 10, 4, 11, 6, 7, 14, 3, 2, 1, 0
70: 13, 12, 9, 15, 8, 10, 5, 11, 6, 7, 14, 4, 3, 2, 1, 0
80: 13, 12, 15, 9, 10, 8, 11, 6, 7, 14, 5, 4, 3, 2, 1, 0
90: 13, 15, 12, 10, 9, 11, 8, 7, 14, 6, 5, 4, 3, 2, 1, 0
100: 15, 13, 12, 10, 11, 9, 8, 14, 7, 6, 5, 4, 3, 2, 1, 0
110: 15, 13, 12, 11, 10, 9, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0
120: 15, 13, 12, 11, 14, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
130: 15, 13, 14, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
135: 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

まず、ステップ数に大きな差があるのが分かりますね。クイックソートは52回、バブルソートは135回と、倍以上差があります。

クイックソートは、一サイクル行ったとき、だいたい半分の配列に分ける事ができます。次のサイクルではその中での並べ替えとなります。

一方、バブルソートは、一サイクル行ったとき、次のサイクルでは末尾の要素一つを除くだけです。このため、処理のステップ数には差が出ます。

詳しく知りたい方はアルゴリズムや計算量に関する書籍をご覧ください。

ソートの過程

では、クイックソートが良く、バブルソートは全く無駄か、というと、そうとは言い切れません。

ソートの過程を見直してみましょう。バブルソートでは、かなり早い段階で、最小の要素0が末尾に来ています。一サイクル処理してしまえば、末尾の要素が最小であることが確定します。

一方、クイックソートは最小の要素が末尾に来るのは比較的遅い事が多いですし、途中の段階では確定していません。

このため、何らかの都合で、20ステップで並べ替えを打ち切る、というような場合、バブルソートであれば最小の要素は判明していますが、クイックソートでは判明していません。

もちろん、「完全に整列されたものが欲しい、その中で処理が速いほうが良い」というケースもあります。一方、「処理時間は限定されている、その中でなるべく役立つ結果を得たい」というケースもあります。

状況によっては、処理の遅いバブルソートが役立つケースもあるかもしれません。用途に応じたソート方法を知っておくとよいでしょう。

CodeIQコード銀行にあなたのコードを預けてみませんか?

  • CodeIQコード銀行ではあなたのコードを財産と考えます。
  • お預かりいただいたコードは、CodeIQコード銀行がしっかり評価し、フィードバックいたします。
  • 当コード銀行にお預けいただいたコードは、企業がみてスカウトをかける可能性があります。
  • 転職したい方や将来転職することを考えている方で、今の自分のスキルレベルを知りたい方はぜひ挑戦してみてください。
  • 企業からスカウトがきたら困る人は挑戦しないでください。

興味を持った方はこちらからチャレンジを!

  • 7
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

レスキューワーク株式会社 水野史土

レスキューワーク株式会社(WordPressサイト/テーマ/プラグインの診断および障害復旧サービス)の代表取締役。。WordPressおよびNovius OS(FuelPHPベースのCMS)のコアコード貢献者。concrete5.orgのコミュニティリーダー。主な著書「徹底攻略 PHP5 技術者認定 [上級] 試験問題集」(共著)。

■関連記事

GUIでアプリケーションが作れるNovius OSで効率的な開発 #PHP... 「アプリケーション作成」ウィザードとは 「アプリケーション作成」ウィザードとは、Novius OSに標準同梱されているアプリケーションです。管理画面からアプリケーションの雛形を作ることができます。開発を効率化するツールとして役立ちます。 このウィザードを使ってアプリケーションの雛形を作ると、 ...
Webサイト発注の指標にもなるconcrete5のポイント機能「Karma」とは? #concret... concrete5とは? concrete5とは、CMS(conctents management system)と呼ばれる、Webサイトをブラウザから更新できるようにするソフトウェアのことです。アメリカ、オレゴン州ポートランドで開発されていますが、英語だけでなく様々な言語に対応しています。日本語...
覚えておくと便利!min, max関数を使ってシンプルなコードを書く方法 #PHP... <Part1> min関数の活用法 min関数は、いくつかの値から最小のものを返す関数です。非常にシンプルですね。シンプルな関数ですが、使い方はいろいろあります。とり得る引数も様々です。 配列を引数にする場合 min関数は配列を引数にすることができます。この場合、配列の要素の中で最も小さい値を...
手軽に開発環境が作れるビルトインサーバーを使ってみよう #PHP... PHPの動作環境構築方法 PHPプログラムは、コマンドラインから実行することができます。しかし、たいていの場合は、ブラウザでアクセスし、実行することが多いでしょう。この場合、ウェブサーバーを用意してアクセスします。以下のように、いろいろな方法があります。 Apache等のウェブサーバーを起動す...
トランプのカードを混ぜる仕組み(パーフェクトシャッフル)をプログラミングで調べてみよう #PHP... トランプのカードを混ぜる トランプゲームを行う時、カードを混ぜる必要があります。カードを混ぜる方法にも、様々なものがありますが、ここでは、リフルシャッフルを取り上げます。 リフルシャッフルは、カード全体を半分に分けて、交互に一枚ずつ混ぜていく、というものです。 実際に手作業で行うと、一度に二、三...
待ったなし!今すぐPHP5.3から移行しないと起こるかもしれないトラブルまとめ #PHP... まずは確認。PHP5.4で削除されるもの セーフモード、マジッククォート、register_globals、register_long_arraysが、PHP5.4で削除されています。これらはPHP5.3で非推奨となっていたものですが、PHP5.2以前ベースで開発していた等で使っている場合はコード...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ