Sort関数などに渡す比較関数（Comparison function）について

March 4, 2023

Dart の Sort や PriorityQueue に渡す比較関数について

sort, PriorityQueue 関数に渡す関数（比較関数）について、いつもどう動くのか頭が混乱するので整理しておく。Dart の sort 関数を例にして記載する。

void main() {
  final List<int> list = [4, 3, 2, 1];
  list.sort((a, b) {
    print('a:$a  b:$b  compare:${a.compareTo(b)}');
    return a.compareTo(b);
  });
	print(list); // [1, 2, 3, 4]
}

// a:4  b:3  compare:1
// a:4  b:2  compare:1
// a:3  b:2  compare:1
// a:4  b:1  compare:1
// a:3  b:1  compare:1
// a:2  b:1  compare:1

以下のサイトに丁寧にまとめられていたので転載する。

JavaScript の sort 関数の使い方を絶対わかるまで解説する

• コールバック関数が 0 未満（例えば-1）を返した場合：aはbの前に来る（順番は変わらない）
• コールバック関数が 0 より大きい値（例えば 1）を返した場合：bはaの前に来る（順番が変わる）
• コールバック関数が 0 を返した場合：何もしない

私は PriorityQueue を使う際の評価関数で同様の点で迷ったので以下に記載する。

import 'package:collection/collection.dart';

void main() {
  final List<int> list = [4, 3, 2, 1];
  final queue = PriorityQueue<int>((a, b) => a.compareTo(b));
  queue.addAll(list);
  print(queue.removeFirst()); // 1
  print(queue.removeFirst()); // 2
  print(queue.removeFirst()); // 3
  print(queue.removeFirst()); // 4
}

compareTo することで優先順位は [1, 2, 3, 4] の順番でキューに格納され、removeFirst() の結果から 1 が最優先で出力され、2, 3, 4 と続いている。以下のように b.compareTo(a) とした場合は [4, 3, 2, 1] の順番で優先度付けされるので、初めに出てくる値は 4 になる。

import 'package:collection/collection.dart';

void main() {
  final List<int> list = [4, 3, 2, 1];
  final queue = PriorityQueue<int>((a, b) => b.compareTo(a));
  queue.addAll(list);
  print(queue.removeFirst()); // 4
  print(queue.removeFirst()); // 3
  print(queue.removeFirst()); // 2
  print(queue.removeFirst()); // 1
}

例えば、３番目に大きな値（以下の例では 2）を出力するには以下のようにすれば良い。

import 'package:collection/collection.dart';

void main() {
  final List<int> list = [4, 3, 2, 1];
  final queue = PriorityQueue<int>((a, b) => a.compareTo(b));
  queue.addAll(list); // [1, 2, 3, 4]

  while (queue.length > 3) {
    queue.removeFirst(); // loop が1回だけ回り、1が除外される
  }

  print(queue.first); // 2 ( 1, 2, 3, 4 の中で 2 は 3番目に大きい数字)
}

以上。