0 だけ末尾になるように並べ替える #Python

3, 4, 0, 1, 2 のような数列を、 1, 2, 3, 4, 0 のように 0 だけ末尾に来るように並べ替えます。この簡単そうに見えて意外と簡単ではないかもしれない問題について解いてみます。

0 を大きな数字に置き換える

並べ替えのキーが 0 の場合だけ Number.MAX_SAFE_INTEGER などの大きい数に置き換えることでソートします。以下は JavaScript (lodash) の例です。

import _ from 'lodash';

const foo = [
  { id: 1, order: 300 },
  { id: 2, order: 0 },
  { id: 3, order: 200 },
];

const sorted = _.orderBy(
  foo,
  [
    // order が 0 の場合だけ、巨大な数字に置き換える
    (item) => item.order === 0 ? Number.MAX_SAFE_INTEGER : item.order,
    'id',
  ]
);

console.log(sorted);

大きい数としては、C# であれば Int32.MaxValue、C++ であれば INT_MAX などが使用できます。使用する型に合わせて適切な値を使用してください。型で許容される最大値が元の配列に含まれていて、より大きいサイズの整数型がない場合、この方法は使用できません。

値が 0 かどうかで最初にソートする

値が 0 かどうかを示す boolean 値をソートキーに含めることで並べ替えを行います。SQL の場合は ORDER BY <column> IS NULL 構文を参考にしてソートします。今回は NULL ではなく 0 なので、ORDER BY <column> = 0 とします。当然インデックスは効かないので、LIMIT などを併用する場合は、次の3つ目の方法も検討してください。

SELECT column_0 as id, column_1 as ord
FROM (VALUES
  ROW(1, 300),
  ROW(2, 0),
  ROW(3, 200)
) AS A
ORDER BY ord = 0, ord, id;

値が 0 の配列とそれ以外に分ける

ソート値が 0 の要素と 0 以外の要素に分けることで並び替えを行います。要するにバケツソートです。

以下は Python の例です。

arr = [
  { 'id': 1, 'order': 300 },
  { 'id': 2, 'order': 0 },
  { 'id': 3, 'order': 200 },
];

sorted_arr = sorted(arr, key=lambda x:[x['order'], x['id']])

is_zero = []
is_not_zero = []

for item in sorted_arr:
  if item['order'] == 0:
    is_zero.append(item)
  else:
    is_not_zero.append(item)

result = [*is_not_zero, *is_zero]
print(result)

SQL の場合、この方法であればインデックスを使用することができるため、サブクエリにも適切に LIMIT を設定すれば計算量を抑えることができます。以下の記事が参考になります。

次のように is null と is not null を無理やり２回に分けた方が速いことがあります。

(select * from t where val is null order by id asc limit 20)
union all
(select * from t where val is not null order by val asc, id asc limit 20)
order by val is null asc, val asc, id asc limit 20;

追記：ユーザー定義の比較関数を使用する (コメントより)

（コメントで提案して頂いた方法がありましたので追記しました。）

言語によっては比較関数を与えることでソートを実行できる場合もあります。

返値は、 2 つの要素の相対順序を示す符号を持つ数値である必要があります。 a が b より小さい場合は負の値、a が b より大きい場合は正の値、等しい場合は 0 とします。

const foo = [
  { id: 1, order: 300 },
  { id: 2, order: 0 },
  { id: 3, order: 200 },
];

const sorted = foo.toSorted(
  (a, b) => (a.order === 0) - (b.order === 0) || a.order - b.order || a.id - b.id
);

console.log(sorted);

【余談】なお、このコードで使われている .toSorted() は ES2023 で導入された比較的新しいメソッドだそうですが、(mozilla.org に掲載されている) モダンなブラウザでは全て実装されているようです。非破壊的に実行する必要がなければ .sort() でも構いません。