Heap Sort
Oct 17, 2012 · Commentscode sortingalgoc++
Heap Sort algo has the following properties:
The top element (root) is always the next in order
This allows you to remove one element at a time (the root) and ensure that you are pulling out items in a sorted order
Always takes O(n*log(n)) time - worst case or best case
- Pros and cons to both
- Pros and cons to both
Simple implementations require additional space to hold heap of size n
Hence space requirement is double of array size n
Not included in big-O notation so something to keep in mind
Not a stable sort
- Original order of equal values may not be maintained
Let’s look at three versions of Heap Sort and see how they compare against each other. We will also find out what differentiates them from each other.
Testing Notes
I compared three versions of of Heap Sort
First version (HeapSort_1) includes logic of sorting items while adding them one by one
Second version (HeapSort_2) and third version (HeapSort_3) are very similar to each other with very minor differences but the performance is different. Still some improvements can be made but for now HeapSort_3 seems to be better
- There’s still scope for both the versions to be better
- There’s still scope for both the versions to be better
Postincrement can be replaced with preincrement in most places which should improve the numbers even more
Code
As usual the code is available here:
https://github.com/abhi1010/Algorithms
Numbers
HeapSort_1
| # of Items in Array | Time Taken | Average for 100 numbers | |
| Random | 10 | 0.013543 | 0.13543 |
| 1K | 3.22043 | 0.322043 | |
| 1M | 4770.14 | 0.477014 | |
| Sorted | 10 | 0.007507 | 0.07507 |
| 1K | 0.625425 | 0.0625425 | |
| 1M | 633.142 | 0.0633142 |
| # of Items in Array | Time Taken | Average for 100 numbers | |
| Random | 10 | 0.019352 | 0.19352 |
| 1K | 3.86284 | 0.386284 | |
| 1M | 8914.22 | 0.891422 | |
| Sorted | 10 | 0.011289 | 0.11289 |
| 1K | 3.49712 | 0.349712 | |
| 1M | 6661.45 | 0.666145 |
| # of Items in Array | Time Taken | Average for 100 numbers | |
| Random | 10 | 0.016266 | 0.16266 |
| 1K | 0.968032 | 0.0968032 | |
| 1M | 900.004 | 0.0900004 | |
| Sorted | 10 | 0.012845 | 0.12845 |
| 1K | 3.08637 | 0.308637 | |
| 1M | 3839.23 | 0.383923 |