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 AbstractSorter with
15 # a custom `compare' function.
20 # This abstract class generalizes ways to sort an array
21 class AbstractSorter[E
: Object]
22 # Compare `a' and `b'.
27 protected meth compare
(a
: E
, b
: E
): Int is abstract
29 # Sort `array' using the `compare' function.
30 meth sort
(array
: Array[E
]) do sub_sort
(array
, 0, array
.length-1
)
32 # Sort `array' between `from' and `to' indices
33 private meth sub_sort
(array
: Array[E
], from
: Int, to
: Int)
37 else if from
+ 7 < to
then
38 quick_sort
(array
, from
, to
)
40 bubble_sort
(array
, from
, to
)
44 # Quick-sort `array' between `from' and `to' indices
45 private meth quick_sort
(array
: Array[E
], from
: Int, to
: Int)
47 var pivot
= array
[from
]
51 while i
<= to
and compare
(array
[i
], pivot
) <= 0 do i
+= 1
52 while j
> i
and compare
(array
[j
], pivot
) >= 0 do j
-= 1
59 array
[from
] = array
[i-1
]
61 sub_sort
(array
, from
, i-2
)
62 sub_sort
(array
, i
, to
)
65 # Bubble-sort `array' between `from' and `to' indices
66 private meth bubble_sort
(array
: Array[E
], from
: Int, to
: Int)
74 if compare
(min_v
, array
[j
]) > 0 then
89 # This class uses the operator <=> to sort arrays.
90 # You can also use the `sort' method of the `Array' class.
91 class ComparableSorter[E
: Comparable]
92 special AbstractSorter[E
]
94 redef meth compare
(a
, b
) do return a
<=> b