Sort records not numbers

Really many texts about sorting show how to sort an array of numbers. Some even evaluate performance of such algorithms.
But real programmers never need to sort a sequence of numbers. In real-world applications only records need to be sorted, using a sort key in such records. A record may be a simple pair of bytes, one being the sort key and the other being the associated value.

This distinction not only affects the actual algorithm code, but often also performance. Of course the asymptotic behavior is not changed, but the actual behavior for a give number of records to sort may depend on the size of the record. Actually some algorithms make fewer key comparisons but more record swaps, others make more key comparisons but fewer record swaps. If a record is just the key number, its swap is quite fast, while if the key is an integer but the record contains some strings or tens of numbers, the time for the key comparions is dwarfed by the time for the record moves.

Advertisements

About Carlo Milanesi

I am a software developer in Italy. I have develop financial, engineering and commercial software using many programming languages, mainly C, C++, Visual Basic, Java, and C#. Now I am interested in Rust and TypeScript.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s