-
-
Notifications
You must be signed in to change notification settings - Fork 426
/
count_sort.dart
71 lines (59 loc) · 1.67 KB
/
count_sort.dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import 'package:test/test.dart';
List<int> countSort(List<int> arr) {
// In case the list is empty, return an empty list
if (arr.length == 0) return [];
int min = arr[0], max = arr[0], i;
List<int> outputArr = [], countArr = [];
for (int i in arr) {
if (i > max) max = i;
if (i < min) min = i;
}
int range = max - min + 1;
// INITIALISING countArr with 0's
for (i = 0; i < range; i++) {
countArr.add(0);
}
for (i = 0; i < arr.length; i++) {
outputArr.add(0);
}
for (i in arr) {
countArr[i - min] += 1;
}
// PREFIX SUM OF countArr
for (i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i - 1];
}
// PUTING VALUES IN SORTED ARRAY
for (i in arr) {
int index = countArr[i - min];
outputArr[index - 1] = i;
countArr[i - min] -= 1;
}
// COPYING VALUES OF SORTED ARRAY INTO ORIGINAL ARRAY
for (i = 0; i < outputArr.length; i++) {
arr[i] = outputArr[i];
}
return arr;
}
int main() {
test("Sorting of empty list returns empty list", () {
expect(countSort([]), equals([]));
});
test("Sorting one element list return same list", () {
expect(countSort([1]), equals([1]));
});
test("Sorting two times doesnt change input", () {
List<int> lst = [5, 7, 1, 10, 54, -1];
expect(countSort(lst), equals(countSort(countSort(lst))));
});
test("Sorting already sorted list returns same list", () {
List<int> lst = [1, 2, 3, 4, 10];
expect(countSort(lst), equals(lst));
});
test("count sort", () {
expect(countSort([34, -2, 122, 24435, 23, 434, 232, 1323]),
equals([-2, 23, 34, 122, 232, 434, 1323, 24435]));
});
print(countSort([-10, -4, 1, 5, 2, -2]));
return 0;
}