1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
5 # This file is free software, which comes along with NIT. This software is
6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
7 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
8 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
9 # is kept unaltered, and a notification of the changes is added.
10 # You are allowed to redistribute it and sell it, alone or is a part of
13 # This module contains classes used to sorts arrays.
14 # In order to provide your own sort class you should define a subclass of `Comparator` with
15 # a custom `Comparator::compare` function.
21 # This abstract class generalizes ways to sort an array
22 interface Comparator[E
]
23 # Compare `a` and `b`.
28 fun compare
(a
: E
, b
: E
): Int is abstract
30 # Sort `array` using the `compare` function.
32 # var s = new DefaultComparator[Int]
33 # var a = [5, 2, 3, 1, 4]
35 # assert a == [1, 2, 3, 4, 5]
36 fun sort
(array
: Array[E
]) do sub_sort
(array
, 0, array
.length-1
)
38 # Sort `array` between `from` and `to` indices
39 private fun sub_sort
(array
: Array[E
], from
: Int, to
: Int)
43 else if from
+ 7 < to
then
44 quick_sort
(array
, from
, to
)
46 bubble_sort
(array
, from
, to
)
50 # Quick-sort `array` between `from` and `to` indices
51 # Worst case: O(n^2), Average case: O(n lg n)
53 # var s = new DefaultComparator[Int]
54 # var a = [5, 2, 3, 1, 4]
55 # s.quick_sort(a, 0, a.length - 1)
56 # assert a == [1, 2, 3, 4, 5]
57 fun quick_sort
(array
: Array[E
], from
: Int, to
: Int) do
58 var pivot
= array
[from
]
62 while i
<= to
and compare
(array
[i
], pivot
) <= 0 do i
+= 1
63 while j
> i
and compare
(array
[j
], pivot
) >= 0 do j
-= 1
70 array
[from
] = array
[i-1
]
72 sub_sort
(array
, from
, i-2
)
73 sub_sort
(array
, i
, to
)
76 # Bubble-sort `array` between `from` and `to` indices
77 # Worst case: O(n^2), average case: O(n^2)
79 # var s = new DefaultComparator[Int]
80 # var a = [5, 2, 3, 1, 4]
81 # s.bubble_sort(a, 0, a.length - 1)
82 # assert a == [1, 2, 3, 4, 5]
83 fun bubble_sort
(array
: Array[E
], from
: Int, to
: Int)
91 if compare
(min_v
, array
[j
]) > 0 then
105 # Insertion-sort `array` between `from` and `to` indices
106 # Worst case: O(n^2), average case: O(n^2)
108 # var s = new DefaultComparator[Int]
109 # var a = [5, 2, 3, 1, 4]
110 # s.insertion_sort(a, 0, a.length - 1)
111 # assert a == [1, 2, 3, 4, 5]
112 fun insertion_sort
(array
: Array[E
], from
: Int, to
: Int) do
113 var last
= array
.length
114 for i
in [from
..to
] do
116 while j
> 0 and compare
(array
[j
], array
[j
- 1]) < 0 do
117 array
.swap_at
(j
, j
- 1)
123 # Merge-sort `array` between `from` and `to` indices
124 # Worst case: O(n lg n), average: O(n lg n)
126 # var s = new DefaultComparator[Int]
127 # var a = [5, 2, 3, 1, 4]
128 # s.merge_sort(a, 0, a.length - 1)
129 # assert a == [1, 2, 3, 4, 5]
130 fun merge_sort
(array
: Array[E
], from
, to
: Int) do
131 if from
>= to
then return
132 var mid
= (to
+ from
) / 2
133 merge_sort
(array
, from
, mid
)
134 merge_sort
(array
, mid
+ 1, to
)
135 merge
(array
, from
, mid
, to
)
138 private fun merge
(array
: Array[E
], from
, mid
, to
: Int) do
140 for i
in [from
..mid
] do l
.add array
[i
]
142 for i
in [mid
+ 1..to
] do r
.add array
[i
]
145 for k
in [from
..to
] do
146 if i
>= l
.length
then
149 else if j
>= r
.length
then
152 else if compare
(l
[i
], r
[j
]) <= 0 then
162 # Heap-sort `array` between `from` and `to` indices
163 # Worst case: O(n lg n), average: O(n lg n)
165 # var s = new DefaultComparator[Int]
166 # var a = [5, 2, 3, 1, 4]
167 # s.heap_sort(a, 0, a.length - 1)
168 # assert a == [1, 2, 3, 4, 5]
169 fun heap_sort
(array
: Array[E
], from
, to
: Int) do
170 var size
= build_heap
(array
)
171 for j
in [from
..to
[ do
172 array
.swap_at
(0, size
)
174 heapify
(array
, 0, size
)
178 private fun build_heap
(array
: Array[E
]): Int do
179 var size
= array
.length
- 1
182 heapify
(array
, i
, size
)
188 private fun heapify
(array
: Array[E
], from
, to
: Int) do
192 if l
< to
and compare
(array
[l
], array
[from
]) > 0 then
197 if r
< to
and compare
(array
[r
], array
[largest
]) > 0 then
200 if largest
!= from
then
201 array
.swap_at
(from
, largest
)
202 heapify
(array
, largest
, to
)
208 # Deprecated class, use `Comparator` instead
209 interface AbstractSorter[E
]
213 # This comparator uses the operator `<=>` to compare objects.
214 # see `default_comparator` for an easy-to-use general stateless default comparator.
215 class DefaultComparator[E
: Comparable]
218 redef fun compare
(a
, b
) do return a
<=> b
223 # Deprecated class, use `DefaultComparator` instead
224 class ComparableSorter[E
: Comparable]
225 super DefaultComparator[E
]
228 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
229 fun default_comparator
: Comparator[Comparable] do return once
new DefaultComparator[Comparable]