Permalink
Fetching contributors…
Cannot retrieve contributors at this time
70 lines (54 sloc) 2.39 KB
// Copyright (c) 2003-2006 King's College London, created by Laurence Tratt
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
//
// Sort 'list' in place into the order determined by 'comparison' using the quickest available
// sorting algorithm. Note that the sort is not guaranteed to be stable.
//
func sort(list, comparison := func (x, y) { return x < y }):
heapsort(list, comparison)
//
// Sort 'list' in place into the order determined by 'comparison' using the heapsort algorithm.
//
func heapsort(list, comparison := func (x, y) { return x < y }):
// This implementation of heapsort is as described at:
//
// http://en.wikipedia.org/wiki/Heapsort
start := list.len().idiv(2) - 1
while start >= 0:
_heapsort_sift(list, comparison, start, list.len())
start := start - 1
end := list.len() - 1
while end > 0:
t := list[0]
list[0] := list[end]
list[end] := t
_heapsort_sift(list, comparison, 0, end)
end := end - 1
func _heapsort_sift(list, comparison, start, count):
while (child := start * 2 + 1) < count:
if child < count - 1 & comparison(list[child], list[child + 1]):
child += 1
if comparison(list[start], list[child]):
t := list[start]
list[start] := list[child]
list[child] := t
start := child
else:
return