tests/example_sorts.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17
  18 fun quicksort(a: Array[Comparable])
  19 do
  20         sub_quicksort(a, 0, a.length-1)
  21 end
  22
  23 fun sub_quicksort(a: Array[Comparable], g: Int, d: Int)
  24 do
  25         if g >= d then
  26                 return
  27         end
  28         var pivot = a[d]
  29         var i = g
  30         var j = d - 1
  31         while j > i do
  32                 while a[i] < pivot do
  33                         i = i + 1
  34                 end
  35                 while j >= g and a[j] >= pivot do
  36                         j = j - 1
  37                 end
  38                 if j > i then
  39                         var t = a[i]
  40                         a[i] = a[j]
  41                         a[j] = t
  42                 end
  43         end
  44         a[d] = a[i]
  45         a[i] = pivot
  46         sub_quicksort(a, g, i-1)
  47         sub_quicksort(a, i+1, d)
  48 end
  49
  50 fun heapsort(a: Array[Comparable])
  51 do
  52         var i = a.length / 2 - 1
  53         while i >= 0 do
  54                 sift_down(a, i, a.length - 1)
  55                 i = i - 1
  56         end
  57
  58         i = a.length - 1
  59         while i >= 1 do
  60                 var t = a[0]
  61                 a[0] = a[i]
  62                 a[i] = t
  63                 sift_down(a, 0, i-1)
  64                 i = i - 1
  65         end
  66 end
  67
  68 fun sift_down(a: Array[Comparable], root: Int, bottom: Int)
  69 do
  70         var done = false
  71         while not done do
  72                 var maxchild = root * 2 + 1
  73                 if maxchild > bottom then
  74                         return
  75                 else if maxchild < bottom and a[maxchild] < a[root * 2 + 2] then
  76                         maxchild = root * 2 + 2
  77                 end
  78
  79                 var r = a[root]
  80                 var c = a[maxchild]
  81                 if r < c then
  82                         a[root] = c
  83                         a[maxchild] = r
  84                         root = maxchild
  85                 else
  86                         done = true
  87                 end
  88         end
  89 end
  90
  91 var q = [6, 7, 3, 9, 1, 4, 2, 8, 5]
  92 var h = [6, 7, 3, 9, 1, 4, 2, 8, 5]
  93 print(q)
  94 quicksort(q)
  95 print(q)
  96 print(h)
  97 heapsort(h)
  98 print(h)