lib/standard/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 AbstractSorter with
  15 # a custom `compare' function.
  16 package sorter
  17
  18 import array
  19
  20 # This abstract class generalizes ways to sort an array
  21 class AbstractSorter[E: Object]
  22         # Compare `a' and `b'.
  23         # Returns:
  24         #       -1 if a < b
  25         #       0  if a = b
  26         #       1  if a > b
  27         protected meth compare(a: E, b: E): Int is abstract
  28
  29         # Sort `array' using the `compare' function.
  30         meth sort(array: Array[E]) do sub_sort(array, 0, array.length-1)
  31
  32         # Sort `array' between `from' and `to' indices
  33         private meth sub_sort(array: Array[E], from: Int, to: Int)
  34         do
  35                 if from >= to then
  36                         return
  37                 else if from + 7 < to then
  38                         quick_sort(array, from, to)
  39                 else
  40                         bubble_sort(array, from, to)
  41                 end
  42         end
  43
  44         # Quick-sort `array' between `from' and `to' indices
  45         private meth quick_sort(array: Array[E], from: Int, to: Int)
  46         do
  47                 var pivot = array[from]
  48                 var i = from
  49                 var j = to
  50                 while j > i do
  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
  53                         if j > i then
  54                                 var t = array[i]
  55                                 array[i] = array[j]
  56                                 array[j] = t
  57                         end
  58                 end
  59                 array[from] = array[i-1]
  60                 array[i-1] = pivot
  61                 sub_sort(array, from, i-2)
  62                 sub_sort(array, i, to)
  63         end
  64
  65         # Bubble-sort `array' between `from' and `to' indices
  66         private meth bubble_sort(array: Array[E], from: Int, to: Int)
  67         do
  68                 var i = from
  69                 while i < to do
  70                         var min = i
  71                         var min_v = array[i]
  72                         var j = i
  73                         while j <= to do
  74                                 if compare(min_v, array[j]) > 0 then
  75                                         min = j
  76                                         min_v = array[j]
  77                                 end
  78                                 j += 1
  79                         end
  80                         if min != i then
  81                                 array[min] = array[i]
  82                                 array[i] = min_v
  83                         end
  84                         i += 1
  85                 end
  86         end
  87 end
  88
  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]
  93         # Return a <=> b
  94         redef meth compare(a, b) do return a <=> b
  95
  96         init do end
  97 end
  98