Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
(added couple of figures with results (links to images)) |
|||
| Line 139: | Line 139: | ||
</code> |
</code> |
||
===Figures: log2( time in microseconds ) vs. log2( sequence length )=== |
===Figures: log2( time in microseconds ) vs. log2( sequence length )=== |
||
N = 1..2**10 |
|||
sort_functions=[builtinsort, insertion_sort, insertion_sort_lowb, qsort, qsortranlc, qsortranpart, qsortranpartis] |
sort_functions = [builtinsort, insertion_sort, insertion_sort_lowb, qsort, qsortranlc, qsortranpart, qsortranpartis] |
||
====ones==== |
====ones==== |
||
[http://bahus.3ka.mipt.ru/gallery/data/public/24.12.07/energy_104231.png ones.png] (143KiB) |
[http://bahus.3ka.mipt.ru/gallery/data/public/24.12.07/energy_104231.png ones.png] (143KiB) |
||
builtinsort - O(N) |
|||
insertion_sort - O(N) |
|||
qsort - O(N**2) |
|||
qsortranpart - O(N) |
|||
====range==== |
====range==== |
||
[http://bahus.3ka.mipt.ru/gallery/data/public/24.12.07/energy_105040.png range.png] (145KiB) |
[http://bahus.3ka.mipt.ru/gallery/data/public/24.12.07/energy_105040.png range.png] (145KiB) |
||
builtinsort - O(N) |
|||
insertion_sort - O(N) |
|||
qsort - O(N**2) |
|||
qsortranpart - O(N*log(N)) |
|||
====shuffled range==== |
|||
[http://bahus.3ka.mipt.ru/gallery/data/public/24.12.07/energy_105620.png shuffledrange.png] (152KiB) |
|||
builtinsort - O(N) ??? |
|||
insertion_sort - O(N**4) ??? |
|||
qsort - O(N*log(N)) |
|||
qsortranpart - O(N) ??? |
|||