PHPでクイックソートを書いてみる

PHP,勉強,転職活動

やってみようと思ったきっかけ

本日企業の面接を受けたところ、「10分ほどでコーディングテストをやります」とのことで初めてコーディングテストというものを受けた。

「クイックソートを実装してください」という問題だった。"クイックソート"というソートの方式(アルゴリズム)を知らなかったため、そこは正直に「そのものを知らないので概要だけでも教えてください」と申し出た。

説明を受けたことで概要は理解をしたが、10分という時間制限や私自身が再帰処理に慣れていなかったこともあって回答としての実装を完成できず時間切れとなってしまった。

後述するが、正解は出せなくとも、面接自体は通った。考え方や適切な質問を行ったことが評価されたらしいとはいえ、解けなかったのが悔しいので家に帰ってから続きを書くこととした。

注意:面接から帰宅して特にネット上のコード等も調べず現状の理解でパパッと実装したので正しいクイックソートになっているかは不明。

とりあえず回答コード

<?php

/**
 * @param array $targets
 *
 * @return array
 */
function quickSort(array $targets): array
{
    if (count($targets) < 2) {
        return $targets;
    }
    $thresholds = [$targets[0]];
    $lessNums = [];
    $greaterNums = [];
    foreach ($targets as $key => $val) {
        if ($key === 0) {
            continue;
        }
        if ($val < $thresholds[0]) {
            $lessNums[] = $val;
        }
        if ($val > $thresholds[0]) {
            $greaterNums[] = $val;
        }
        if ($val === $thresholds[0]) {
            $thresholds[] = $val;
        }
    }
    return array_merge(quickSort($lessNums), $thresholds, quickSort($greaterNums));
}

$data1 = range(0, 5);
$data2 = range(0, 10);
shuffle($data1);
shuffle($data2);

$inputs = array_merge($data1, $data2);
var_dump(quickSort($inputs));

解説

得られた前提

受けた概要説明によると、クイックソートはランダムな数値配列から値を一つ取り出し、それを基準として、それより小さいものの配列とそれより大きいものの配列をつくるのだとか。

その説明から"それを再帰的に繰り返して処理すれば全ての値をソートできる"、というところが勘所なんだろうなと考えた。

ソート対象配列作成部分

まずはfunction部分ではなくソートするためのターゲット配列を作っているところから解説する。

$data1 = range(0, 5);
$data2 = range(0, 10);
shuffle($data1);
shuffle($data2);

$inputs = array_merge($data1, $data2);
var_dump(quickSort($inputs));

$data1,$data2を作成している理由は「値が重複した場合」を再現するため。それらをshuffleして$inputsとしてマージすることで以下のような重複あり&&非ソート状態の配列が作られる。

array(17) {
  [0]=>
  int(5)
  [1]=>
  int(4)
  [2]=>
  int(1)
  [3]=>
  int(0)
  [4]=>
  int(2)
  [5]=>
  int(3)
  [6]=>
  int(9)
  [7]=>
  int(6)
  [8]=>
  int(10)
  [9]=>
  int(7)
  [10]=>
  int(4)
  [11]=>
  int(3)
  [12]=>
  int(2)
  [13]=>
  int(5)
  [14]=>
  int(0)
  [15]=>
  int(1)
  [16]=>
  int(8)
}

ちなみに、特に課題として重複した場合の処理もしろ、と指定されたわけではない。

最後の一行はソート実行部分。

関数部分

/**
 * @param array $targets
 *
 * @return array
 */
function quickSort(array $targets): array
{
    if (count($targets) < 2) {
        return $targets;
    }
    $thresholds = [$targets[0]];
    $lessNums = [];
    $greaterNums = [];
    foreach ($targets as $key => $val) {
        if ($key === 0) {
            continue;
        }
        if ($val < $thresholds[0]) {
            $lessNums[] = $val;
        }
        if ($val > $thresholds[0]) {
            $greaterNums[] = $val;
        }
        if ($val === $thresholds[0]) {
            $thresholds[] = $val;
        }
    }
    return array_merge(quickSort($lessNums), $thresholds, quickSort($greaterNums));
}

ポイントは、頭のif文。こちらが終了条件。ソート対象の要素数が2未満(1以下)だった場合にはそのままリターン。

count($targets) === 1 というような条件にしてしまうと要素0の場合が弾けないので少し注意が必要。

その後のthresholdsというのは比較元の数値(閾値)を格納する配列。基準値、閾値、比較元等なんと呼べばいいか分からなかったのでとりあえずthresholdという名前を採用した。

lessNums配列は閾値より小さい数値が入る配列。greaterNumsは閾値より大きい数値が入る配列。ここで配列として初期化しておかないと、後にarray_mergeする際にnullを渡してしまいwarning等が出る可能性があるのでそこは少し注意。ちなみに命名規則として配列は複数形にする、という習慣からこのような名前にしているが、英文法的に正しいのかは不明。English is too difficult for me. もしかするとleft,rightとしてもわかりやすいかもしれない。

foreachのループ部分はそれぞれ判定してlessNums,greaterNumsに値をpushしている。頭の$key === 0は閾値を閾値自身と比較する必要がないため早期continue処理。

コアとなる部分は最後のreturn部分。array_mergeによって小さい側の配列, 閾値配列, 大きい側の配列をマージしているのだが、小さい側と大きい側の配列を再帰的に処理することでそれぞれソートをかけている。

再起処理なので最下部の処理から追った方が良い気もするが、とりあえず処理を上から順に追って説明すると

// 1周目(最上位処理)
1. $targets = [4,3,4,5,2,3]; // とりあえずこれが初期値だとする
2. $thresholds = [4];        // $thresholds = $targets[0]部分
3. $lessNums = [3,2,3];      // 判定結果をpushしたらこうなる
4. $greaterNums = [5];       // 同上
5. $thresholds = [4,4];      // 同数があったのでthresholdsにpush. 最上位(大元の)thresholds
6. return array_merge(quickSort([3,2,3]), [4,4], quickSort([5])); // 再帰処理の結果は[2,3,3,4,4,5]が返る

// 2周目(小さい側)
1. $targets = [3,2,3];
2. $thresholds = [3];
3. $lessNums = [2];
4. $greaterNums = [];
5. $thresholds = [3,3];    // 同数があったのでthresholdsにpush. 下位処理のthresholds
6. return array_merge(quickSort([2]), [3,3], quickSort([])); // [2,3,3]が返る

// 3周目(小さい側)
1. $targets = [2];
2. count($targets) < 2 なのでreturn $targetsして終了 // 最上位の処理からみた小さい側配列は[2,3,3]

// 2周目(大きい側)
1. $targets = [5];
2. count($targets) < 2 なのでreturn $targetsして終了

// 最上位の処理に戻るとこんな形になっている
array_merge([2,3,3], [4,4], [5]); // 結果は[2,3,3,4,4,5]となってソートされている

わかりにくいかもしれないが、私なりに最大限わかりやすく書くとこういった感じ。

改めて注意したいのは、このページやコードはクイックソートについて詳細に調べたりはせず、本日面接の中で頂戴した概要説明から理解した内容で書いているので本来のクイックソートとはニュアンスが違う可能性があるので注意されたし。

コーディングテストを初めて受けた感想

今回は何の準備も予習もせず受けることになったので、まさかテストがあるとは面食らった。求人情報には載っていたのかもしれないがチェックが漏れていたのでまずはそこを反省。

実際のテストを受けてみて思ったことは、現状持っている知識やコードの技術というより、考え方を見られているのかな、と感じた。実際、面談の場では上記コードの70%位しか記述できず、再帰処理の部分をうまく実装できなかったので解答は完成さえしていない。したがって動作確認も行っていない。そもそもホワイトボードに擬似コードを書くのでも良いという話だった。

テストに合格するポイントとしては、「考えていることを喋りまくる」ことが重要なのではないかと思う。「基本的に再帰処理を使って作るのだとあたりをつけている」、「最終的には小さい側と閾値と大きい側をマージしたい」、「閾値と同値の場合の処理が書けていないが、それはあとで考える」等、面接官に対して今考えていることを言葉で説明し続けた。アウトプットをすることで「重要なポイントには気付けているので、時間を与えれば完成させられそうだな」と面接官に印象付けることが大事なのかと思う。同値処理の課題や終了条件をどう設定するか、という重要そうなところは頭でロジックを組みながら気付いた瞬間に口に出すよう心がけた。

なにはともあれ合格できてよかった。入社するかどうかは検討中だが、貴重な体験をさせてもらいました。

PHP,勉強,転職活動

Posted by shoopon