Now that you understand some of the fundamental data structures used in today's software applications, you can use those data structures to organize the large amounts of data that your applications need to process. Sorting data into a logical order is a critical prerequisite for many of the algorithms in the chapters to come, and it is such a potential performance bottleneck that an enormous amount of research has been done over many decades to determine the most efficient way to sort various types of data. This chapter introduces three sorting algorithms that are easy to implement and are best suited to smaller sets of data, as their performance is
O(N2). Chapter 7 covers more complex sorting algorithms with better performance characteristics for very large data sets.
This chapter discusses the following:
The importance of sorting
The role of comparators
How the bubble sort algorithm works
How the selection sort algorithm works
How the insertion sort algorithm works
The meaning of stability
The pros and cons of the basic sorting algorithms
You already know from the real world how important sorting is when working with searching algorithms. To look up a word in a dictionary, you use an algorithm: You open the dictionary at a point roughly equivalent to the word's position in the sorted list of all the words in the dictionary. You then do a few quick narrowing searches until you find the page it's on, and then finally scan the page for the ...