Zenn
🐘

PHPのsort()って何順なの？

2024/05/09に公開
Go
PHP
sort
tech

sort関数の仕組み

PHPのsort関数で次のような配列を渡したらどのようにソートされるんでしょうか。本記事ではそういう話をします。

sort関数をゆっくり紐解いていきます。

<?php
$a = ["1"," A3"," 2"];
sort($a);

sort関数について

はじめにsort関数の使い方を復習します。こんな感じに使います。

<?php
// php.net から引用
$a = ['lemon','banana','apple'];
sort($a);
print_r($a);

// Array
// (
//     [0] => apple
//     [1] => banana
//     [2] => lemon
// )

sort関数には第二引数があり、省略すると SORT_REGULAR という比較関数を使ってソートされます。他に SORT_NATURAL などいくつかありますが、本記事では SORT_REGULAR の話をします。
またstring型同士の比較のみの話をします。

sort(array &$array, int $flags = SORT_REGULAR): true

PHPのソート処理を知るには、大きく次の3つのことを意識する必要があります。
この3つを順に解説していきます。

  1. 文字列の解析
  2. 文字列同士の比較（比較関数）
  3. ソート処理（ソートアルゴリズム）

1. 文字列の解析

複数の文字列をソートしていく為に、まずはソートしようとしている文字列がどういう文字列かを調べるところから始まります。

ざっくりいうと「整数」「浮動小数点数」「それ以外」の3種類に分類します。

数値っぽいものは数値とみなすようになっていて、少し変わった例をあげると次のようなものがあります。この例では 0-9 以外の文字が含まれていたとしても数値とみなされるケースと、そうでないケースを紹介しています。

もう少し具体的な話をすると、この判定の実装方法は次の図のようになっていて、文字列を左側から順にチェックしていき、基本的に数字だけで構成されていれば「整数」、途中にドットがあれば「浮動小数点数」、「それ以外」の3種類に分類されます。

2. 文字列同士の比較（比較関数）

上述の通り文字列を解析したら、今度はそれに基づいて文字列同士を比較していきます。
具体的には次のように比較します。

  • 両方とも数値（LONG, DOUBLE）とみなすことができれば数値として比較する
  • そうでなければバイナリとして比較する

これにより、どちらの文字列が大きいかを判別できるので、あとはこれにもとづいて並び替える事ができそうですね。それではソート処理に話を進めます。

3. ソート処理（ソートアルゴリズム）

PHP7以降のソート処理では配列の要素数が16以下のときは挿入ソート、そうでなければクイックソートを使ってソートを行う実装になっています。

php-srcで言うとzend_sort()と言う関数になるので、こちらのソースをご覧いただければ詳しいソートアルゴリズムが分かります。

https://github.com/php/php-src/blob/0a0e8064e044b133da423952d8e78d50c4841a2e/Zend/zend_sort.c#L248-L306

sort関数を理解できた！

ここまでで説明した比較関数とソートアルゴリズムを組み合わせることでソート処理を行うことができるようになります。大まかな説明になりますが、これがPHPのsort関数の仕組みです。

実際にsort関数を使った例をいくつかあげると、次の結果を得られます。ここまでの説明を読むことで、なぜこのような結果が得られるのかざっくりとイメージを掴めるようになったと思います。

<?php
$a = ["3", "2", "1"]; sort($a); // ["1","2","3"]
$a = ["+1.1","1","-1.2"]; sort($a); // [“-1.2”, ”1”, ”+1.1”]
$a = ["C","B","A"]; sort($a);; // [“A”,” B”,”C”]

矛盾した比較関数

さてここで一番最初に例に挙げた [“1”,” 2"," A3"] という組み合わせの配列をソートするとどうなるか、と言う話に戻します。

PHP8でこれをソートしてみると、次の結果になりました。

<?php
$a = ["1"," A3"," 2"];
sort($a); // [" 2"," A3”,"1"]

では今度はソート前の配列の順番を入れ替えたパターンを用意して実行してみましょう。すると今度はソート前の並び方によってソート結果が変わってしまいました。

一見規則性がなさそうでランダムで結果が変わっているようにしか見えませんが、この並び順も実は理由があります。

<?php
$a = ["1"," 2"," A3"];
sort($a); // ["1"," 2"," A3"]

$a = [" A3","1"," 2"];
sort($a); // [" A3","1"," 2"]

$a = ["1"," A3"," 2"];
sort($a); // [" 2"," A3”,"1"]

比較関数では2つの文字列同士を比較することになりますが、この3つの文字列を比較すると次のような結果になります。

  • "1" < " 2" // true (数値と見なせるので数値として比較)
  • " 2" < " A3" // true (片方は数値ではないのでバイナリで比較)
  • " A3" < "1" // true (片方は数値ではないのでバイナリで比較)

上記結果をシンプルに表現すると、次のような状況が成り立ってしまっています。（AがCより大きいのは不自然）

  • A < B
  • B < C
  • C < A

これをもう少し違う形に書き換えると、そもそもこれをソートすることが不可能な事が分かると思います。

  • A < B < C < A < B < C < ...

以上の通りPHPのSORT_REGULARという比較関数を使うとこのような矛盾した結果が返る事がありますが、この場合のソート結果はソートアルゴリズムに依存することになります。
したがってこの一見ランダムにしか見えないソート結果も、PHPのソートアルゴリズムにしたがってソートされた結果だったということになります。

まとめ

ここまでで解説した内容をまとめると次のようになります。

  • PHPのSORT_REGULARは数値とみなせる場合は数値とみなして比較し、それ以外はバイナリとして比較する
  • PHPのSORT_REGULARで使っている比較関数は矛盾した結果を返すケースがある
  • この矛盾した比較関数を使った場合、ソート結果はソートアルゴリズムに依存する
  • PHPのバージョンが上がると内部仕様が変わるので、ソート結果が変わる可能性がある

原理的が分かったので、PHP内部で使っている比較関数とソートアルゴリズムの両方を移植すれば、違う言語でも同じソート順を再現可能な気がしますね。

ということで、ここまでの内容をGoに移植してみたところ、ちゃんとPHPのソートを再現することができました。

GoでPHPのソートを再現したくなったときはこちらを使ってみて下さい（必要になることがあるか分かりませんが）。
https://github.com/demouth/phpsort-go

	// このように使える
	strings := []string{
		"lemon",
		"apple",
		“1”,
		“+2”,
		“03”,
	}
	phpsort.Sort(strings)

以上です

参考資料

Discussion