Dartのsortは、順番が変わるので気をつけたほうがいい話

はじめに

Dartのsortを使ってハマったので記事にします。

問題のコード

Listのsortを使っています。

items.sort((a, b) {
  if(a.isDone == b.isDone) {
    return 0;
  }
  return a.isDone ? 1 : -1;
});
for (final item in items) {
  print(item.name);
}

class Item {
  Item({required this.name, required this.isDone});
  final String name;
  final bool isDone;
}

何が問題か

記事のタイトルにも書いてあるとおり、Dartのsortは順番が保証されないため、元のリストから並び順が変わってしまいます。
この問題はリストの要素数が大きくなると発生するみたいです。

以下を実行してみると、

void main() {
  final items = [
    Item(name: 'A', isDone: false),
    Item(name: 'B', isDone: false),
    Item(name: 'C', isDone: false),
    Item(name: 'D', isDone: false),
    Item(name: 'E', isDone: false),
    Item(name: 'F', isDone: false),
    Item(name: 'G', isDone: false),
    Item(name: 'H', isDone: false),
    Item(name: 'I', isDone: false),
    Item(name: 'J', isDone: false),
    Item(name: 'K', isDone: false),
    Item(name: 'L', isDone: false),
    Item(name: 'M', isDone: false),
    Item(name: 'N', isDone: false),
    Item(name: 'O', isDone: false),
    Item(name: 'P', isDone: false),
    Item(name: 'Q', isDone: false),
    Item(name: 'R', isDone: false),
    Item(name: 'S', isDone: false),
    Item(name: 'T', isDone: false),
    Item(name: 'U', isDone: false),
    Item(name: 'V', isDone: false),
    Item(name: 'W', isDone: false),
    Item(name: 'X', isDone: false),
    Item(name: 'Y', isDone: false),
    Item(name: 'Z', isDone: false),
    Item(name: 'AA', isDone: false),
    Item(name: 'BB', isDone: false),
    Item(name: 'CC', isDone: false),
    Item(name: 'DD', isDone: false),
    Item(name: 'EE', isDone: false),
    Item(name: 'FF', isDone: false),
    Item(name: 'GG', isDone: false),
    Item(name: 'HH', isDone: false),
    Item(name: 'II', isDone: false),
    Item(name: 'JJ', isDone: false),
  ];

  items.sort((a, b) {
    if (a.isDone == b.isDone) {
      return 0;
    }
    return a.isDone ? 1 : -1;
  });
  for (final item in items) {
    print(item.name);
  }
}

class Item {
  Item({required this.name, required this.isDone});
  final String name;
  final bool isDone;
}

出力は下記のような順番になります。(抜粋してます)

GG
B
C
D
E
F
G
H
I
J
K
II
M
N
O
P
Q
R
S
T
U
.
.
.

解決方法

方法①：グループ分けして結合する

final sorted = [
  ...items.where((e) => !e.isDone),
  ...items.where((e) => e.isDone),
];

メリット

• 順序が絶対に維持される
• 計算量 O(n)
• 意図が明確で読みやすい

方法②：mergeSortを使う

collectionのmergeSortは順番が保証される安定ソートなので、順番は変わりません。

import 'package:collection/collection.dart';

void main() {
  final items = [
    Item(name: 'A', isDone: false),
    Item(name: 'B', isDone: false),
    Item(name: 'C', isDone: false),
    Item(name: 'D', isDone: false),
    Item(name: 'E', isDone: false),
    Item(name: 'F', isDone: false),
    Item(name: 'G', isDone: false),
    Item(name: 'H', isDone: false),
    Item(name: 'I', isDone: false),
    Item(name: 'J', isDone: false),
    Item(name: 'K', isDone: false),
    Item(name: 'L', isDone: false),
    Item(name: 'M', isDone: false),
    Item(name: 'N', isDone: false),
    Item(name: 'O', isDone: false),
    Item(name: 'P', isDone: false),
    Item(name: 'Q', isDone: false),
    Item(name: 'R', isDone: false),
    Item(name: 'S', isDone: false),
    Item(name: 'T', isDone: false),
    Item(name: 'U', isDone: false),
    Item(name: 'V', isDone: false),
    Item(name: 'W', isDone: false),
    Item(name: 'X', isDone: false),
    Item(name: 'Y', isDone: false),
    Item(name: 'Z', isDone: false),
    Item(name: 'AA', isDone: false),
    Item(name: 'BB', isDone: false),
    Item(name: 'CC', isDone: false),
    Item(name: 'DD', isDone: false),
    Item(name: 'EE', isDone: false),
    Item(name: 'FF', isDone: false),
    Item(name: 'GG', isDone: false),
    Item(name: 'HH', isDone: false),
    Item(name: 'II', isDone: false),
    Item(name: 'JJ', isDone: false),
  ];

  mergeSort(
    items,
    compare: (a, b) {
      if (a.isDone == b.isDone) {
        return 0;
      }
      return a.isDone ? 1 : -1;
    },
  );
  for (final item in items) {
    print(item.name);
  }
}