O'Reilly logo

The Art of Concurrency by Clay Breshears

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 8. Sorting

image with no caption

This chapter examines the operation of concurrent sorting. At times, sorting has been estimated to account for over 80% of all processing cycles. Presenting the results from database queries, compiling a list of business investments with associated risk-reward measures, and figuring the company payroll are all operations that require sorting. Even with the large amounts of processing time spent on graphical interfaces, visualization processing, and video games, sorting remains a vital part of computation. Every time you get a list of URLs from a search engine, the results have been sorted, typically by some measure of relevance to your original query.

In this chapter I will first consider compare-exchange sorts. These are sorting algorithms that use the results from comparing two keys to determine the relative order of the elements with those keys. Movement of data items will be based on those results and will be the exchange of the positions of the two items under consideration. The final algorithm considered is radix sort, which compares bits within keys to determine movement of data. Example codes presented in this chapter will use arrays of integers, but you can apply these techniques to structures with a key field to distinguish between elements.

Bubblesort

Bubblesort was the first sorting algorithm I ever learned. It is easy to code and simple to understand. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required