#
# This file is free software, which comes along with NIT. This software is
# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
-# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
# PARTICULAR PURPOSE. You can modify it is you want, provided this header
# is kept unaltered, and a notification of the changes is added.
# You are allowed to redistribute it and sell it, alone or is a part of
# a custom `Comparator::compare` function.
module sorter
+import range
import array
# This abstract class generalizes ways to sort an array
interface Comparator[E]
# Compare `a` and `b`.
# Returns:
- # -1 if a < b
+ # -1 if a < b
# 0 if a = b
# 1 if a > b
fun compare(a: E, b: E): Int is abstract
# Sort `array` using the `compare` function.
+ #
+ # var s = new DefaultComparator[Int]
+ # var a = [5, 2, 3, 1, 4]
+ # s.sort(a)
+ # assert a == [1, 2, 3, 4, 5]
fun sort(array: Array[E]) do sub_sort(array, 0, array.length-1)
# Sort `array` between `from` and `to` indices
end
# Quick-sort `array` between `from` and `to` indices
- private fun quick_sort(array: Array[E], from: Int, to: Int)
- do
+ # Worst case: O(n^2), Average case: O(n lg n)
+ #
+ # var s = new DefaultComparator[Int]
+ # var a = [5, 2, 3, 1, 4]
+ # s.quick_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun quick_sort(array: Array[E], from: Int, to: Int) do
var pivot = array[from]
var i = from
var j = to
sub_sort(array, from, i-2)
sub_sort(array, i, to)
end
-
+
# Bubble-sort `array` between `from` and `to` indices
- private fun bubble_sort(array: Array[E], from: Int, to: Int)
+ # Worst case: O(n^2), average case: O(n^2)
+ #
+ # var s = new DefaultComparator[Int]
+ # var a = [5, 2, 3, 1, 4]
+ # s.bubble_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun bubble_sort(array: Array[E], from: Int, to: Int)
do
var i = from
while i < to do
i += 1
end
end
+
+ # Insertion-sort `array` between `from` and `to` indices
+ # Worst case: O(n^2), average case: O(n^2)
+ #
+ # var s = new DefaultComparator[Int]
+ # var a = [5, 2, 3, 1, 4]
+ # s.insertion_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun insertion_sort(array: Array[E], from: Int, to: Int) do
+ var last = array.length
+ for i in [from..to] do
+ var j = i
+ while j > 0 and compare(array[j], array[j - 1]) < 0 do
+ array.swap_at(j, j - 1)
+ j -= 1
+ end
+ end
+ end
+
+ # Merge-sort `array` between `from` and `to` indices
+ # Worst case: O(n lg n), average: O(n lg n)
+ #
+ # var s = new DefaultComparator[Int]
+ # var a = [5, 2, 3, 1, 4]
+ # s.merge_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun merge_sort(array: Array[E], from, to: Int) do
+ if from >= to then return
+ var mid = (to + from) / 2
+ merge_sort(array, from, mid)
+ merge_sort(array, mid + 1, to)
+ merge(array, from, mid, to)
+ end
+
+ private fun merge(array: Array[E], from, mid, to: Int) do
+ var l = new Array[E]
+ for i in [from..mid] do l.add array[i]
+ var r = new Array[E]
+ for i in [mid + 1..to] do r.add array[i]
+ var i = 0
+ var j = 0
+ for k in [from..to] do
+ if i >= l.length then
+ array[k] = r[j]
+ j += 1
+ else if j >= r.length then
+ array[k] = l[i]
+ i += 1
+ else if compare(l[i], r[j]) <= 0 then
+ array[k] = l[i]
+ i += 1
+ else
+ array[k] = r[j]
+ j += 1
+ end
+ end
+ end
+
+ # Heap-sort `array` between `from` and `to` indices
+ # Worst case: O(n lg n), average: O(n lg n)
+ #
+ # var s = new DefaultComparator[Int]
+ # var a = [5, 2, 3, 1, 4]
+ # s.heap_sort(a, 0, a.length - 1)
+ # assert a == [1, 2, 3, 4, 5]
+ fun heap_sort(array: Array[E], from, to: Int) do
+ var size = build_heap(array)
+ for j in [from..to[ do
+ array.swap_at(0, size)
+ size -= 1
+ heapify(array, 0, size)
+ end
+ end
+
+ private fun build_heap(array: Array[E]): Int do
+ var size = array.length - 1
+ var i = size / 2
+ while i >= 0 do
+ heapify(array, i, size)
+ i -= 1
+ end
+ return size
+ end
+
+ private fun heapify(array: Array[E], from, to: Int) do
+ var l = from * 2
+ var r = l + 1
+ var largest: Int
+ if l < to and compare(array[l], array[from]) > 0 then
+ largest = l
+ else
+ largest = from
+ end
+ if r < to and compare(array[r], array[largest]) > 0 then
+ largest = r
+ end
+ if largest != from then
+ array.swap_at(from, largest)
+ heapify(array, largest, to)
+ end
+ end
+
end
# Deprecated class, use `Comparator` instead
nitlanguage / nit.git / commitdiff