d0233740d16ccb69beecc347a3bf49b5acbd1a64
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 `AbstractSorter::compare` function.
20 # This abstract class generalizes ways to sort an array
21 # TODO: rename `AbstractSorter` to `Comparator`
22 interface AbstractSorter[E
]
23 # Compare `a` and `b`.
28 fun compare
(a
: E
, b
: E
): Int is abstract
30 # Sort `array` using the `compare` function.
31 fun sort
(array
: Array[E
]) do sub_sort
(array
, 0, array
.length-1
)
33 # Sort `array` between `from` and `to` indices
34 private fun sub_sort
(array
: Array[E
], from
: Int, to
: Int)
38 else if from
+ 7 < to
then
39 quick_sort
(array
, from
, to
)
41 bubble_sort
(array
, from
, to
)
45 # Quick-sort `array` between `from` and `to` indices
46 private fun quick_sort
(array
: Array[E
], from
: Int, to
: Int)
48 var pivot
= array
[from
]
52 while i
<= to
and compare
(array
[i
], pivot
) <= 0 do i
+= 1
53 while j
> i
and compare
(array
[j
], pivot
) >= 0 do j
-= 1
60 array
[from
] = array
[i-1
]
62 sub_sort
(array
, from
, i-2
)
63 sub_sort
(array
, i
, to
)
66 # Bubble-sort `array` between `from` and `to` indices
67 private fun bubble_sort
(array
: Array[E
], from
: Int, to
: Int)
75 if compare
(min_v
, array
[j
]) > 0 then
90 # This class uses the operator <=> to sort arrays.
91 # You can also use the `sort` method of the `Array` class.
92 class ComparableSorter[E
: Comparable]
93 super AbstractSorter[E
]
95 redef fun compare
(a
, b
) do return a
<=> b