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.
20 # This abstract class generalizes ways to sort an array
21 interface Comparator[E
]
22 # Compare `a` and `b`.
27 fun compare
(a
: E
, b
: E
): Int is abstract
29 # Sort `array` using the `compare` function.
30 fun sort
(array
: Array[E
]) do sub_sort
(array
, 0, array
.length-1
)
32 # Sort `array` between `from` and `to` indices
33 private fun 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 fun 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 fun bubble_sort
(array
: Array[E
], from
: Int, to
: Int)
74 if compare
(min_v
, array
[j
]) > 0 then
89 # Deprecated class, use `Comparator` instead
90 interface AbstractSorter[E
]
94 # This comparator uses the operator `<=>` to compare objects.
95 # see `default_comparator` for an easy-to-use general stateless default comparator.
96 class DefaultComparator[E
: Comparable]
99 redef fun compare
(a
, b
) do return a
<=> b
104 # Deprecated class, use `DefaultComparator` instead
105 class ComparableSorter[E
: Comparable]
106 super DefaultComparator[E
]
109 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
110 fun default_comparator
: Comparator[Comparable] do return once
new DefaultComparator[Comparable]