Heapsort

Keywords: algorithms sorting
Created: 2020-05-28 Thu 22:51
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 heapsort_60277f59bca266ff515f112accb026e527a03246.svg comparisons on average, bottom-up-heapsort only needs heapsort_1ffc618e092f3301d32d361b95e5600253bb9f0a.svg .

n heapsort_f6f96afefea9771b121611f920859e51c46d211b.svg heapsort_341448671da3905a2e2b55b0204bb6e633876d0f.svg
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.

heapsort_gray.png

Last export: 2020-06-30 Tue 13:44
This document is also available as plain text and pdf.

If you have an idea how this page could be improved or a comment send me a mail.