Applications of Sorting

 

An important key to algorithm design is to use sorting as a basic building block, because once a set of items is sorted, many other problems become easy. Consider the following applications:  

• Searching - Binary search enables you to test whether an item is in a dictionary in time, once the keys are all sorted. Search preprocessing is perhaps the single most important application of sorting.
• Closest pair - Given a set of n numbers, how do you find the pair of numbers that have the smallest difference between them? After the numbers are sorted, the closest pair of numbers will lie next to each other somewhere in sorted order. Thus a linear-time scan through them completes the job, for a total of time including the sorting.  
• Element uniqueness - Are there any duplicates in a given a set of n items? The most efficient algorithm is to sort them and then do a linear scan though them checking all adjacent pairs. This is a special case of the closest-pair problem above, where we ask if there is a pair separated by a gap of zero.  
• Frequency distribution - Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting. To find out how often an arbitrary element k occurs, start by looking up k using binary search in a sorted array of keys. By walking to the left of this point until the element is not k and then walking to the right, we can find this count in time, where c is the number of occurrences of k. The number of instances of k can be found in time by using binary search to look for the positions of both and , where is arbitrarily small, and then taking the difference of these positions.  
• Selection - What is the kth largest item in the set? If the keys are placed in sorted order in an array, the kth largest can be found in constant time by simply looking at the kth position of the array. In particular, the median element (see Section ) appears in the (n/2)nd position in sorted order.  

   
  Figure: Constructing the convex hull of points in the plane  
  

• Convex hulls - Given n points in two dimensions, what is the polygon of smallest area that contains them all? The convex hull is like a rubber band stretched over the points in the plane and then released. It compresses to just cover the points, as shown in Figure . The convex hull gives a nice representation of the shape of the points and is the most important building block for more sophisticated geometric algorithms, as discussed in catalog Section .  

  But how can we use sorting to construct the convex hull? Once you have the points sorted by x-coordinate, the points can be inserted from left to right into the hull. Since the rightmost point is always on the boundary, we know that it will be inserted into the hull. Adding this new rightmost point might cause others to be deleted, but we can quickly identify these points because they lie inside the polygon formed by adding the new point. These points to delete will be neighbors of the previous point we inserted, so they will be easy to find. The total time is linear after the sorting has been done.

While some of these problems (particularly median and selection) can be solved in linear time using more sophisticated algorithms, sorting provides quick and easy solutions to all of these problems. It is a rare application whose time complexity is such that sorting proves to be the bottleneck, especially a bottleneck that could have otherwise been removed using more clever algorithmics. Don't ever be afraid to spend time sorting whenever you use an efficient sorting routine.