lib/standard/collection/sorter.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
   4 #
   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
  11 # another product.
  12
  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.
  16 module sorter
  17
  18 import range
  19 import array
  20
  21 # This abstract class generalizes ways to sort an array
  22 interface Comparator[E]
  23         # Compare `a` and `b`.
  24         # Returns:
  25         #       -1 if a < b
  26         #       0  if a = b
  27         #       1  if a > b
  28         fun compare(a: E, b: E): Int is abstract
  29
  30         # Sort `array` using the `compare` function.
  31         #
  32         #     var s = new DefaultComparator[Int]
  33         #     var a = [5, 2, 3, 1, 4]
  34         #     s.sort(a)
  35         #     assert a == [1, 2, 3, 4, 5]
  36         fun sort(array: Array[E]) do sub_sort(array, 0, array.length-1)
  37
  38         # Sort `array` between `from` and `to` indices
  39         private fun sub_sort(array: Array[E], from: Int, to: Int)
  40         do
  41                 if from >= to then
  42                         return
  43                 else if from + 7 < to then
  44                         quick_sort(array, from, to)
  45                 else
  46                         bubble_sort(array, from, to)
  47                 end
  48         end
  49
  50         # Quick-sort `array` between `from` and `to` indices
  51         # Worst case: O(n^2), Average case: O(n lg n)
  52         #
  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]
  59                 var i = from
  60                 var j = to
  61                 while j > i do
  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
  64                         if j > i then
  65                                 var t = array[i]
  66                                 array[i] = array[j]
  67                                 array[j] = t
  68                         end
  69                 end
  70                 array[from] = array[i-1]
  71                 array[i-1] = pivot
  72                 sub_sort(array, from, i-2)
  73                 sub_sort(array, i, to)
  74         end
  75
  76         # Bubble-sort `array` between `from` and `to` indices
  77         # Worst case: O(n^2), average case: O(n^2)
  78         #
  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)
  84         do
  85                 var i = from
  86                 while i < to do
  87                         var min = i
  88                         var min_v = array[i]
  89                         var j = i
  90                         while j <= to do
  91                                 if compare(min_v, array[j]) > 0 then
  92                                         min = j
  93                                         min_v = array[j]
  94                                 end
  95                                 j += 1
  96                         end
  97                         if min != i then
  98                                 array[min] = array[i]
  99                                 array[i] = min_v
 100                         end
 101                         i += 1
 102                 end
 103         end
 104
 105         # Insertion-sort `array` between `from` and `to` indices
 106         # Worst case: O(n^2), average case: O(n^2)
 107         #
 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
 115                         var j = i
 116                         while j > 0 and compare(array[j], array[j - 1]) < 0 do
 117                                 array.swap_at(j, j - 1)
 118                                 j -= 1
 119                         end
 120                 end
 121         end
 122
 123         # Merge-sort `array` between `from` and `to` indices
 124         # Worst case: O(n lg n), average: O(n lg n)
 125         #
 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)
 136         end
 137
 138         private fun merge(array: Array[E], from, mid, to: Int) do
 139                 var l = new Array[E]
 140                 for i in [from..mid] do l.add array[i]
 141                 var r = new Array[E]
 142                 for i in [mid + 1..to] do r.add array[i]
 143                 var i = 0
 144                 var j = 0
 145                 for k in [from..to] do
 146                         if i >= l.length then
 147                                 array[k] = r[j]
 148                                 j += 1
 149                         else if j >= r.length then
 150                                 array[k] = l[i]
 151                                 i += 1
 152                         else if compare(l[i], r[j]) <= 0 then
 153                                 array[k] = l[i]
 154                                 i += 1
 155                         else
 156                                 array[k] = r[j]
 157                                 j += 1
 158                         end
 159                 end
 160         end
 161
 162         # Heap-sort `array` between `from` and `to` indices
 163         # Worst case: O(n lg n), average: O(n lg n)
 164         #
 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)
 173                         size -= 1
 174                         heapify(array, 0, size)
 175                 end
 176         end
 177
 178         private fun build_heap(array: Array[E]): Int do
 179                 var size = array.length - 1
 180                 var i = size / 2
 181                 while i >= 0 do
 182                         heapify(array, i, size)
 183                         i -= 1
 184                 end
 185                 return size
 186         end
 187
 188         private fun heapify(array: Array[E], from, to: Int) do
 189                 var l = from * 2
 190                 var r = l + 1
 191                 var largest: Int
 192                 if l < to and compare(array[l], array[from]) > 0 then
 193                         largest = l
 194                 else
 195                         largest = from
 196                 end
 197                 if r < to and compare(array[r], array[largest]) > 0 then
 198                         largest = r
 199                 end
 200                 if largest != from then
 201                         array.swap_at(from, largest)
 202                         heapify(array, largest, to)
 203                 end
 204         end
 205
 206 end
 207
 208 # Deprecated class, use `Comparator` instead
 209 interface AbstractSorter[E]
 210         super Comparator[E]
 211 end
 212
 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]
 216         super Comparator[E]
 217         # Return a <=> b
 218         redef fun compare(a, b) do return a <=> b
 219
 220         init do end
 221 end
 222
 223 # Deprecated class, use `DefaultComparator` instead
 224 class ComparableSorter[E: Comparable]
 225         super DefaultComparator[E]
 226 end
 227
 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]