Channels ▼
RSS

C/C++

Algorithm Improvement through Performance Measurement: Part 4



Algorithm Improvement through Performance Measurement: Part 1

Algorithm Improvement through Performance Measurement: Part 2

Algorithm Improvement through Performance Measurement: Part 3

Algorithm Improvement through Performance Measurement: Part 4

Algorithm Improvement through Performance Measurement: Part 5


The In-place Hybrid MSD N-bit-Radix Sort I presented in In-place Hybrid N-bit-Radix Sort was developed as a combination of Radix Sort, Insertion Sort, and Counting Sort. This algorithm sorts arrays of integers (8, 16, 32, and 64-bit, unsigned and signed), and significantly outperforms STL sort(), which is a hybrid combination of QuickSort, Heap Sort, and Insertion Sort. In-place Hybrid MSD N-bit-Radix Sort algorithm uses a recursive Radix Sort technique based on the most-significant-digit (MSD). It sorts based on the MSD first, followed by the next digit and so on until all digits have been used for sorting. The algorithm has a nice property of being in-place (not requiring extra memory), but lacks being stable.

Stable algorithms resolve ties between array elements by placing the element that appeared first in the input array as first in the output array. Stability is not necessary when sorting only numbers, as it is impossible to differentiate the result which was sorted using a stable algorithm from one sorted using a non-stable algorithm. In this article, I develop and optimize a stable version of the MSD Radix Sort since stability is useful in cases of sorting other than only numbers.

Stable MSD Radix Sort Concept

The following discussion illustrates how an MSD Radix Sort works with decimal numbers. In this case, the radix is 10, and Decimal-Radix sorting is being performed (10-Radix Sort).

Three numbers start with a zero ( 07, 09, 01 ), four numbers start with a one (13, 15, 15, 19), three numbers start with a two (22, 28, 21 ), none start with a three, two numbers start with a four (45, 42).

Use an output array of equal size to the input array, and split it into bins that hold 3 elements, 4 elements, 3 elements, and 2 elements (as we just counted).

Place all numbers that started with zeros into the bin zero, all numbers that started with ones into the bin one, that started with twos into bin two, and so on.

Sort each of these bins based on the second digit

Create an output array of equal size for each input bin:

Place all numbers that have the second digit equal to a one in bin one, all numbers that have the second digit equal to two in bin two, and so on.

Assemble all of the bins together into a single sorted array

Note this procedure took two passes over all of the array elements: one pass for the left-most digit, and the second pass for the second digit; because each element was made of two digits in this example. The algorithm takes two passes over the entire array no matter how many elements are in the array to be sorted. Thus, run time is linear in order, times the number of digits in the elements -O( dn ), where d is the number of digits and n is the number of elements in the array.


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.
 

Video