Channels ▼
RSS

.NET

Algorithm Performance


Graphs

In the series, graphs showed execution time. Another way to view performance is by throughput — the number of elements/second that are processed (sorted). The following logarithmic graphs show performance of various sequential and parallel algorithms in elements/second. Keep in mind that several algorithms are hybrid, where Insertion Sort is combined with the main sorting algorithm, and is the reason for performance being nearly the same for the smallest array size. Note that the order of the algorithms is visible on these graphs, especially O(n2), where as the difference between O(nlgn) and O(dn) is smaller.

In all graphs the vertical axis is elements/second and the horizontal axis is size of the array being sorted. All measurements are for Intel i7 860 quad-core CPU (2.8 GHz).

Figure 1: 8-bit unsigned elements.

Figure 2: 16-bit unsigned elements.

Figure 3: 32-bit unsigned elements.

Figure 4: 64-bit unsigned elements.

Figure 5: 8-bit unsigned elements.

Figure 6: 16-bit unsigned elements.

Figure 7: 32-bit unsigned elements.

Figure 8: 64-bit unsigned elements.

References

Parallel In-Place N-bit-Radix Sort

Quality of Random Numbers versus Performance

In-Place Hybrid Binary-Radix Sort

Optimizing Performance of Sorting Algorithms (Insertion and Selection Sort)

In-Place Hybrid N-bit-Radix Sort

Counting Sort Performance

Parallel Counting Sort

Parallel Counting Sort, Part 2

Stable Hybrid MSD N-bit-Radix Sort


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

.NET Recent Articles

Video

Upcoming Events



Most Recent Premium Content