PHPでクイックソートのアルゴリズム

BLOG ENTRY

PHPでクイックソートのアルゴリズム

php

基本的なソートアルゴリズムのクイックソートのプログラムメモ。

<?php

    /*
    * クイックソート
    * $numArr    = ソートする配列
    * $left      = 開始位置（0で決め打ち）
    * $right     = 終了位置（$numArrの要素数）
    * $order     = ソートの昇順(ASC)・降順(DESC) デフォルトは昇順
    */
    function quickSort(&$numArr, $left = 0, $right, $order = "ASC") {

        //要素数が1以下であれば
        //ソートをする必要がないので処理を終了する。
        if ($left >= $right) {
            return;
        }

        swap ($numArr, $left, ceil(($left+$right)/2));
        $last = $left;

        for ($i=$left+1; $i<=$right; $i++) {

            if ($order == "ASC") {

                if ($numArr[$i] < $numArr[$left]) {
                    swap($numArr, ++$last, $i);
                }

            } else {

                if ($numArr[$i] >$numArr[$left]) {

                    swap($numArr, ++$last, $i);

                }
            }
        }

        swap($numArr, $left, $last);
        quickSort($numArr, $left,   $last-1, $order = $order);
        quickSort($numArr, $last+1, $right,  $order = $order);
    }
    //要素を入れ替える関数
    function swap(&$v, $i, $j) {
        $temp  = $v[$i];
        $v[$i] = $v[$j];
        $v[$j] = $temp;
    }

    //ソート対象の配列
    $numArr    = array(92, 15, 26, 86, 105, 54, 29, 42, 75);

    echo "ソート前";
    echo "<pre>";
    print_r($numArr);
    echo "</pre>";

    quickSort($numArr, 0, count($numArr)-1, $order="DESC");

    echo "ソート後";
    echo "<pre>";
    print_r($numArr);

以上。

comments(0)