Heap Sort

[calo_mir 10]

Heap Sort

MIL/DEV 720

This package provides an implementation of the heap sort algorithm.

The algorithm is an in-place, unstable sort with O(n log n) performance in all cases. Essentially, the algorithm has

performance competitive with quicksort but without quicksort's dangerous O(n^2) worst case performance.

The implementation provides a general function that takes an array of arbitrary objects and a comparison function to

compare those objects. Convenience functions are provided to sort arrays of integers.

Usage example:

_input  = [5, 3, 1, 2, 4];
_output = [_input] call M720_heap_sort_integers_ascending;
assert (_output == [1, 2, 3, 4, 5]);

Downloads

Download (0.1.2) MD5 SHA256 PGP signature

Changelog

2010-07-20 version: heap_sort 0.1.0

2010-07-21 code: Re-indented and fixed trailing whitespace.

2010-07-21 code: Automate versioning and build example mission.

2010-07-21 version: heap_sort 0.1.1

2010-07-27 meta: Repack to use PKZIP.

2010-07-27 version: heap_sort 0.1.2

[CarlGustaffa 3]

Neat. One question; what are the differences between heap sort, insert sort, and shell sort (ref this post). I mean, can you try to explain where (in Arma uses) you would choose one method over the others? Or maybe; are there applications where you wouldn't use a particular method, and why.

[Serclaes 0]

Mainly runtime since i doubt you are ever going to handle much memory relevant data.

It's hard to formulate a specific case. Let's say you are sure to have a long array, you'd select an algorithm that has low runtime in high numbers. If you can have logarithmic runtime, that's what you want.

Insert sort for example has n² runtime. Heapsort has n*log(n). But heapsort is not stable. That means that if the array contains equal elements there is no way to tell which one will be first. A stable sort would keep the order.

If you already have a sorted array, you might want to use something like bubble or insert sort which then would have O(n) runtime.

[rübe 118]

If you already have a sorted array, you might want to use something like bubble or insert sort which then would have O(n) runtime.

FPDR :D

Bubble sort is never the answer. Did I hear bubble sort? You might aswell go for a bogo sort if you're that nuts! :D

Really, bubble sort was a bad, nasty joke. That so many teachers still dare to show this to their students only shows how cruel (or stupid, but that's the same thing in the ned) comp. science teachers may be. hehe. There was a brilliant rant somewhere on the internets, but I can't find it again unfortunately. Well, here is a good rant too, but there was even a better one.. mhh

Btw. Watch this fascinating video: http://www.youtube.com/watch?v=AUn7-36oluU&feature=related (yeah, computer science rocks that hard! :cool:)

Edited July 28, 2010 by ruebe
NOOOOOOOOOOOOOOOO!!!!111elf