Table of Contents
Number of Comparisons
Average over 100 runs on randomized arrays.
| Elements | Std. | Bottom Up |
|---|---|---|
| 1 | 0.00 | 0.00 |
| 2 | 1.00 | 1.00 |
| 4 | 6.50 | 6.88 |
| 8 | 25.73 | 23.63 |
| 16 | 80.83 | 66.38 |
| 32 | 223.06 | 170.24 |
| 64 | 571.49 | 410.45 |
| 128 | 1397.09 | 959.03 |
| 256 | 3305.29 | 2184.31 |
| 512 | 7636.22 | 4891.30 |
| 1024 | 17315.34 | 10822.84 |
Standard-heapsort needs around
comparisons on average,
bottom-up-heapsort only needs
.
| n |
|
|
|---|---|---|
| 1 | 0.0 | 0.0 |
| 2 | 4.0 | 2.0 |
| 4 | 16.0 | 8.0 |
| 8 | 48.0 | 24.0 |
| 16 | 128.0 | 64.0 |
| 32 | 320.0 | 160.0 |
| 64 | 768.0 | 384.0 |
| 128 | 1792.0 | 896.0 |
| 256 | 4096.0 | 2048.0 |
| 512 | 9216.0 | 4608.0 |
| 1024 | 20480.0 | 10240.0 |
Visualizations
Standard-heapsort run on an a list
[0, 1, 2, ..., 255]
.
After each comparison a new row is added.
