blob: 657fe1246ce21e08273a4cfeb654d6b5aab66dd7 [file] [log] [blame]
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
library sort_helper;
import "package:expect/expect.dart";
typedef Sorter = void Function(List<num>);
typedef Comparer = int Function(num, num);
class SortHelper {
SortHelper(this.sortFunction, this.compareFunction) {}
void run() {
testSortIntLists();
testSortDoubleLists();
}
bool isSorted(List<num> a) {
for (int i = 1; i < a.length; i++) {
if (compareFunction(a[i - 1], a[i]) > 0) {
return false;
}
}
return true;
}
void testSortIntLists() {
var a = new List<int>.filled(40, -1);
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
testSort(a);
for (int i = 0; i < a.length; i++) {
a[a.length - i - 1] = i;
}
testSort(a);
for (int i = 0; i < 21; i++) {
a[i] = 1;
}
for (int i = 21; i < a.length; i++) {
a[i] = 2;
}
testSort(a);
// Same with bad pivot-choices.
for (int i = 0; i < 21; i++) {
a[i] = 1;
}
for (int i = 21; i < a.length; i++) {
a[i] = 2;
}
a[6] = 1;
a[13] = 1;
a[19] = 1;
a[25] = 1;
a[33] = 2;
testSort(a);
for (int i = 0; i < 21; i++) {
a[i] = 2;
}
for (int i = 21; i < a.length; i++) {
a[i] = 1;
}
testSort(a);
// Same with bad pivot-choices.
for (int i = 0; i < 21; i++) {
a[i] = 2;
}
for (int i = 21; i < a.length; i++) {
a[i] = 1;
}
a[6] = 2;
a[13] = 2;
a[19] = 2;
a[25] = 2;
a[33] = 1;
testSort(a);
var a2 = new List<int>.empty();
testSort(a2);
var a3 = new List<int>.filled(1, 1);
testSort(a3);
// --------
// Test insertion sort.
testInsertionSort(0, 1, 2, 3);
testInsertionSort(0, 1, 3, 2);
testInsertionSort(0, 3, 2, 1);
testInsertionSort(0, 3, 1, 2);
testInsertionSort(0, 2, 1, 3);
testInsertionSort(0, 2, 3, 1);
testInsertionSort(1, 0, 2, 3);
testInsertionSort(1, 0, 3, 2);
testInsertionSort(1, 2, 3, 0);
testInsertionSort(1, 2, 0, 3);
testInsertionSort(1, 3, 2, 0);
testInsertionSort(1, 3, 0, 2);
testInsertionSort(2, 0, 1, 3);
testInsertionSort(2, 0, 3, 1);
testInsertionSort(2, 1, 3, 0);
testInsertionSort(2, 1, 0, 3);
testInsertionSort(2, 3, 1, 0);
testInsertionSort(2, 3, 0, 1);
testInsertionSort(3, 0, 1, 2);
testInsertionSort(3, 0, 2, 1);
testInsertionSort(3, 1, 2, 0);
testInsertionSort(3, 1, 0, 2);
testInsertionSort(3, 2, 1, 0);
testInsertionSort(3, 2, 0, 1);
}
void testSort(List<num> a) {
sortFunction(a);
Expect.isTrue(isSorted(a));
}
void testInsertionSort(int i1, int i2, int i3, int i4) {
var a = new List<int>.filled(4, -1);
a[0] = i1;
a[1] = i2;
a[2] = i3;
a[3] = i4;
testSort(a);
}
void testSortDoubleLists() {
var a = new List<double>.filled(40, -1);
for (int i = 0; i < a.length; i++) {
a[i] = 1.0 * i + 0.5;
}
testSort(a);
for (int i = 0; i < a.length; i++) {
a[i] = 1.0 * (a.length - i) + 0.5;
}
testSort(a);
for (int i = 0; i < a.length; i++) {
a[i] = 1.5;
}
testSort(a);
}
Sorter sortFunction;
Comparer compareFunction;
}