Why Sorting Data Is Important for Algorithms
Imagine trying to find an item in a list without sorting it first. Every search becomes a time-consuming sequential search. But, a case can be made for not sorting data for algorithms. After all, the data is still accessible, even if you don’t sort it — and sorting takes time.
Of course, the problem with unsorted data is the same problem as that junk drawer in your kitchen (or wherever you have your junk drawer — assuming that you can find it at all). Looking for anything in the junk drawer is time consuming because you can’t even begin to guess where to find something. Rather than just reach in and take what you want, you must take out myriad other items that you don’t want in an effort to find the one item you need. Unfortunately, the item you need might not be in the junk drawer in the first place—you might have thrown it out or put it in a different drawer.
The junk drawer in your home is just like unsorted data on your system. When the data is unsorted, you need to search one item at a time, and you don’t even know whether you’ll find what you need without searching every item in the dataset first. It’s a frustrating way to work with data.
Of course, simply sorting the data isn’t enough. If you have an employee database sorted by last name, yet need to look up an employee by birth date, the sorting isn’t useful. (Say you want to find all of the employees who have a birthday on a certain day.) To find the birth date you need, you must still search the entire dataset one item at a time. Consequently, sorting must focus on a particular need. Yes, you needed the employee database sorted by department at one point and by last name at another time, but now you need it sorted by birth date in order to use the dataset effectively.
The need to maintain several sorted orders for the same data is the reason that developers created indexes. Sorting a small index is faster than sorting the entire dataset. The index maintains a specific data order and points to the full dataset so that you can find what you need extremely fast. By maintaining an index for each sort requirement, you can effectively cut data access time and allow several people to access the data at the same time in the order in which they need to access it.
Many ways are available to categorize sorting algorithms. One of these ways is the speed of the sort. When considering how effective a particular sort algorithm is at arranging the data, timing benchmarks typically look at two factors:
- Comparisons: To move data from one location in a dataset to another, you need to know where to move it, which means comparing the target data to other data in the dataset. Having fewer comparisons means better performance.
- Exchanges: Depending on how you write an algorithm, the data may not get to its final location in the dataset on the first try. The data might actually move several times. The number of exchanges affects speed considerably because now you’re actually moving data from one location to another in memory. Fewer and smaller exchanges (such as when using indexes) means better performance.