Chapter 4

Sorting

Applications of Sorting: Numbers

4.1. The Grinch is given the job of partitioning [math]\displaystyle{ 2n }[/math] players into two teams of [math]\displaystyle{ n }[/math] players each. Each player has a numerical rating that measures how good he or she is at the game. The Grinch seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between the teams. Show how the Grinch can do the job in [math]\displaystyle{ O(n log n) }[/math] time.

Solution

4.2. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, [math]\displaystyle{ S = {6, 13, 19, 3, 8} }[/math], 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.

(a) Let [math]\displaystyle{ S }[/math] be an unsorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that maximizes [math]\displaystyle{ |x-y| }[/math]. Your algorithm must run in [math]\displaystyle{ O(n) }[/math] worst-case time.

(b) Let [math]\displaystyle{ S }[/math] be a sorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that maximizes [math]\displaystyle{ |x - y| }[/math]. Your algorithm must run in [math]\displaystyle{ O(1) }[/math] worst-case time.

(c) Let [math]\displaystyle{ S }[/math] be an unsorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that minimizes [math]\displaystyle{ |x - y| }[/math], for [math]\displaystyle{ x \neq y }[/math]. Your algorithm must run in [math]\displaystyle{ O(n log n) }[/math] worst-case time.

(d) Let [math]\displaystyle{ S }[/math] be a sorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that minimizes [math]\displaystyle{ |x - y| }[/math], for [math]\displaystyle{ x \neq y }[/math]. Your algorithm must run in [math]\displaystyle{ O(n) }[/math] worst-case time.

4.3. Take a list of [math]\displaystyle{ 2n }[/math] real numbers as input. Design an [math]\displaystyle{ O(n log n) }[/math] algorithm that partitions the numbers into [math]\displaystyle{ n }[/math] pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus, the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

Solution

4.4. Assume that we are given [math]\displaystyle{ n }[/math] pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an [math]\displaystyle{ O(n) }[/math] algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

4.5. The mode of a bag of numbers is the number that occurs most frequently in the set. The set {4, 6, 2, 4, 3, 1} has a mode of 4. Give an efficient and correct algorithm to compute the mode of a bag of [math]\displaystyle{ n }[/math] numbers.

Solution

4.6. Given two sets [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math] (each of size [math]\displaystyle{ n }[/math]), and a number [math]\displaystyle{ x }[/math], describe an [math]\displaystyle{ O(n log n) }[/math] algorithm for finding whether there exists a pair of elements, one from [math]\displaystyle{ S_1 }[/math] and one from [math]\displaystyle{ S_2 }[/math], that add up to [math]\displaystyle{ x }[/math]. (For partial credit, give a [math]\displaystyle{ \Theta(n^2) }[/math] algorithm for this problem.)

4.7. Give an efficient algorithm to take the array of citation counts (each count is a non-negative integer) of a researcher’s papers, and compute the researcher’s [math]\displaystyle{ h }[/math]-index. By definition, a scientist has index [math]\displaystyle{ h }[/math] if [math]\displaystyle{ h }[/math] of his or her [math]\displaystyle{ n }[/math] papers have been cited at least [math]\displaystyle{ h }[/math] times, while the other [math]\displaystyle{ n-h }[/math] papers each have no more than [math]\displaystyle{ h }[/math] citations.

Solution

4.8. Outline a reasonable method of solving each of the following problems. Give the order of the worst-case complexity of your methods.

(a) You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills. Find out who did not pay.

(b) You are given a printed list containing the title, author, call number, and publisher of all the books in a school library and another list of thirty publishers. Find out how many of the books in the library were published by each company.

(c) You are given all the book checkout cards used in the campus library during the past year, each of which contains the name of the person who took out the book. Determine how many distinct people checked out at least one book.

4.9. Given a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] integers and an integer [math]\displaystyle{ T }[/math], give an [math]\displaystyle{ O(n^{k-1}log n) }[/math] algorithm to test whether [math]\displaystyle{ k }[/math] of the integers in [math]\displaystyle{ S }[/math] add up to [math]\displaystyle{ T }[/math].

Solution

4.10. We are given a set of [math]\displaystyle{ S }[/math] containing [math]\displaystyle{ n }[/math] real numbers and a real number [math]\displaystyle{ x }[/math], and seek efficient algorithms to determine whether two elements of [math]\displaystyle{ S }[/math] exist whose sum is exactly [math]\displaystyle{ x }[/math].

(a) Assume that [math]\displaystyle{ S }[/math] is unsorted. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm for the problem.

(b) Assume that [math]\displaystyle{ S }[/math] is sorted. Give an [math]\displaystyle{ O(n) }[/math] algorithm for the problem.

4.11. Design an [math]\displaystyle{ O(n) }[/math] algorithm that, given a list of [math]\displaystyle{ n }[/math] elements, finds all the elements that appear more than [math]\displaystyle{ n/2 }[/math] times in the list. Then, design an [math]\displaystyle{ O(n) }[/math] algorithm that, given a list of [math]\displaystyle{ n }[/math] elements, finds all the elements that appear more than [math]\displaystyle{ n/4 }[/math] times.

Solution

Applications of Sorting: Intervals and Sets

4.12. Give an efficient algorithm to compute the union of sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], where [math]\displaystyle{ n = max(|A|, |B|) }[/math]. The output should be an array of distinct elements that form the union of the sets.

(a) Assume that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are unsorted arrays. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm for the problem.

(b) Assume that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are sorted arrays. Give an [math]\displaystyle{ O(n) }[/math] algorithm for the problem.

4.13. A camera at the door tracks the entry time [math]\displaystyle{ a_i }[/math] and exit time [math]\displaystyle{ b_i }[/math] (assume [math]\displaystyle{ b_i \gt a_i }[/math]) for each of [math]\displaystyle{ n }[/math] persons [math]\displaystyle{ p_i }[/math] attending a party. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm that analyzes this data to determine the time when the most people were simultaneously present at the party. You may assume that all entry and exit times are distinct (no ties).

Solution

4.14. Given a list [math]\displaystyle{ I }[/math] of [math]\displaystyle{ n }[/math] intervals, specified as [math]\displaystyle{ (x_i, y_i) }[/math] pairs, return a list where the overlapping intervals are merged. For [math]\displaystyle{ I = {(1, 3),(2, 6),(8, 10),(7, 18)} }[/math] the output should be [math]\displaystyle{ {(1, 6),(7, 18)} }[/math]. Your algorithm should run in worst-case [math]\displaystyle{ O(n log n) }[/math] time complexity.

4.15. You are given a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] intervals on a line, with the [math]\displaystyle{ i }[/math]th interval described by its left and right endpoints [math]\displaystyle{ (l_i, r_i) }[/math]. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm to identify a point [math]\displaystyle{ p }[/math] on the line that is in the largest number of intervals.

As an example, for [math]\displaystyle{ S = {(10, 40),(20, 60),(50, 90),(15, 70)} }[/math] no point exists in all four intervals, but [math]\displaystyle{ p = 50 }[/math] is an example of a point in three intervals. You can assume an endpoint counts as being in its interval.

Solution

4.16. You are given a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] segments on the line, where segment [math]\displaystyle{ S_i }[/math] ranges from [math]\displaystyle{ l_i }[/math] to [math]\displaystyle{ r_i }[/math]. Give an efficient algorithm to select the fewest number of segments whose union completely covers the interval from 0 to [math]\displaystyle{ m }[/math].

Heaps

4.17. Devise an algorithm for finding the [math]\displaystyle{ k }[/math] smallest elements of an unsorted set of [math]\displaystyle{ n }[/math] integers in [math]\displaystyle{ O(n + k log n) }[/math].

Solution

4.18. Give an [math]\displaystyle{ O(n log k) }[/math]-time algorithm that merges [math]\displaystyle{ k }[/math] sorted lists with a total of [math]\displaystyle{ n }[/math] elements into one sorted list. (Hint: use a heap to speed up the obvious [math]\displaystyle{ O(know) }[/math]-time algorithm).

4.19. You wish to store a set of [math]\displaystyle{ n }[/math] numbers in either a max-heap or a sorted array. For each application below, state which data structure is better, or if it does not matter. Explain your answers.

(a) Find the maximum element quickly.

(b) Delete an element quickly.

(c) Form the structure quickly.

(d) Find the minimum element quickly.

Solution

4.20. (a) Give an efficient algorithm to find the second-largest key among [math]\displaystyle{ n }[/math] keys. You can do better than [math]\displaystyle{ 2n - 3 }[/math] comparisons.

(b) Then, give an efficient algorithm to find the third-largest key among [math]\displaystyle{ n }[/math] keys. How many key comparisons does your algorithm do in the worst case? Must your algorithm determine which key is largest and second-largest in the process?

Quicksort

4.21. Use the partitioning idea of quicksort to give an algorithm that finds the median element of an array of [math]\displaystyle{ n }[/math] integers in expected [math]\displaystyle{ O(n) }[/math] time. (Hint: must you look at both sides of the partition?)

Solution

4.22. The median of a set of [math]\displaystyle{ n }[/math] values is the [math]\displaystyle{ [n/2] }[/math]th smallest value.

(a) Suppose quicksort always pivoted on the median of the current sub-array. How many comparisons would quicksort make then in the worst case?

(b) Suppose quicksort always pivoted on the [math]\displaystyle{ [n/3] }[/math]th smallest value of the current sub-array. How many comparisons would be made then in the worst case?

4.23. Suppose an array [math]\displaystyle{ A }[/math] consists of [math]\displaystyle{ n }[/math] elements, each of which is red, white, or blue'. We seek to sort the elements so that all the reds come before all the whites, which come before all the blues. The only operations permitted on the keys are:

• Examine([math]\displaystyle{ A,i }[/math]) – report the color of the [math]\displaystyle{ i }[/math]th element of [math]\displaystyle{ A }[/math].

• Swap([math]\displaystyle{ A,i,j }[/math]) – swap the [math]\displaystyle{ i }[/math]th element of [math]\displaystyle{ A }[/math] with the [math]\displaystyle{ j }[/math]th element.

Find a correct and efficient algorithm for red–white–blue sorting. There is a linear-time solution.

Solution

4.24. Give an efficient algorithm to rearrange an array of [math]\displaystyle{ n }[/math] keys so that all the negative keys precede all the non-negative keys. Your algorithm must be in-place, meaning you cannot allocate another array to temporarily hold the items. How fast is your algorithm?

4.25. Consider a given pair of different elements in an input array to be sorted, say [math]\displaystyle{ z_i }[/math] and [math]\displaystyle{ z_j }[/math] . What is the most number of times [math]\displaystyle{ z_i }[/math] and [math]\displaystyle{ z_j }[/math] might be compared with each other during an execution of quicksort?

Solution

4.26. Define the recursion depth of quicksort as the maximum number of successive recursive calls it makes before hitting the base case. What are the minimum and maximum possible recursion depths for randomized quicksort?

4.27. Suppose you are given a permutation [math]\displaystyle{ p }[/math] of the integers 1 to [math]\displaystyle{ n }[/math], and seek to sort them to be in increasing order [math]\displaystyle{ [1, . . . , n] }[/math]. The only operation at your disposal is reverse[math]\displaystyle{ (p,i,j) }[/math], which reverses the elements of a subsequence [math]\displaystyle{ p_i, . . . , p_j }[/math] in the permutation. For the permutation [1, 4, 3, 2, 5] one reversal (of the second through fourth elements) suffices to sort.

• Show that it is possible to sort any permutation using [math]\displaystyle{ O(n) }[/math] reversals.

• Now suppose that the cost of reverse[math]\displaystyle{ (p,i,j) }[/math] is equal to its length, the number of elements in the range, [math]\displaystyle{ |j - i| + 1 }[/math]. Design an algorithm that sorts [math]\displaystyle{ p }[/math] in [math]\displaystyle{ O(n log^2 n) }[/math] cost. Analyze the running time and cost of your algorithm and prove correctness.

Solution

Mergesort

4.28. Consider the following modification to merge sort: divide the input array into thirds (rather than halves), recursively sort each third, and finally combine the results using a three-way merge subroutine. What is the worst-case running time of this modified merge sort?

4.29. Suppose you are given [math]\displaystyle{ k }[/math] sorted arrays, each with [math]\displaystyle{ n }[/math] elements, and you want to combine them into a single sorted array of [math]\displaystyle{ kn }[/math] elements. One approach is to use the merge subroutine repeatedly, merging the first two arrays, then merging the result with the third array, then with the fourth array, and so on until you merge in the [math]\displaystyle{ k }[/math]th and final input array. What is the running time?

Solution

4.30. Consider again the problem of merging [math]\displaystyle{ k }[/math] sorted length-[math]\displaystyle{ n }[/math] arrays into a single sorted length-[math]\displaystyle{ kn }[/math] array. Consider the algorithm that first divides the [math]\displaystyle{ k }[/math] arrays into [math]\displaystyle{ k/2 }[/math] pairs of arrays, and uses the merge subroutine to combine each pair, resulting in [math]\displaystyle{ k/2 }[/math] sorted length-[math]\displaystyle{ 2n }[/math] arrays. The algorithm repeats this step until there is only one length-[math]\displaystyle{ know }[/math] sorted array. What is the running time as a function of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math]?

Other Sorting Alogrithims

4.31. Stable sorting algorithms leave equal-key items in the same relative order as in the original permutation. Explain what must be done to ensure that mergesort is a stable sorting algorithm.

Solution

4.32. Wiggle sort: Given an unsorted array [math]\displaystyle{ A }[/math], reorder it such that [math]\displaystyle{ A[0] \lt A[1] \gt A[2] \lt A[3] . . . . }[/math] For example, one possible answer for input [3, 1, 4, 2, 6, 5] is [1, 3, 2, 5, 4, 6]. Can you do it in [math]\displaystyle{ O(n) }[/math] time using only [math]\displaystyle{ O(1) }[/math] space?

4.33. Show that [math]\displaystyle{ n }[/math] positive integers in the range 1 to [math]\displaystyle{ k }[/math] can be sorted in [math]\displaystyle{ O(n log k) }[/math] time. The interesting case is when [math]\displaystyle{ k \ll n }[/math].

Solution

4.34. Consider a sequence [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] integers with many duplications, such that the number of distinct integers in [math]\displaystyle{ S }[/math] is [math]\displaystyle{ O(log n) }[/math]. Give an [math]\displaystyle{ O(n log log n) }[/math] worst-case time algorithm to sort such sequences.

4.35. Let [math]\displaystyle{ A[1..n] }[/math] be an array such that the first [math]\displaystyle{ n - \sqrt n }[/math] elements are already sorted (though we know nothing about the remaining elements). Give an algorithm that sorts [math]\displaystyle{ A }[/math] in substantially better than [math]\displaystyle{ n log n }[/math] steps.

Solution

4.36. Assume that the array [math]\displaystyle{ A[1..n] }[/math] only has numbers from [math]\displaystyle{ {1, . . . , n^2} }[/math] but that at most [math]\displaystyle{ log log n }[/math] of these numbers ever appear. Devise an algorithm that sorts [math]\displaystyle{ A }[/math] in substantially less than [math]\displaystyle{ O(n log n) }[/math].

4.37. Consider the problem of sorting a sequence of [math]\displaystyle{ n }[/math] 0’s and 1’s using comparisons. For each comparison of two values [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], the algorithm learns which of [math]\displaystyle{ x \lt y, x = y }[/math], or [math]\displaystyle{ x \gt y }[/math] holds.

(a) Give an algorithm to sort in [math]\displaystyle{ n - 1 }[/math] comparisons in the worst case. Show that your algorithm is optimal.

(b) Give an algorithm to sort in [math]\displaystyle{ 2n/3 }[/math] comparisons in the average case (assuming each of the [math]\displaystyle{ n }[/math] inputs is 0 or 1 with equal probability). Show that your algorithm is optimal.

Solution

4.38. Let [math]\displaystyle{ P }[/math] be a simple, but not necessarily convex, [math]\displaystyle{ n }[/math]-sided polygon and [math]\displaystyle{ q }[/math] an arbitrary point not necessarily in [math]\displaystyle{ P }[/math]. Design an efficient algorithm to find a line segment originating from [math]\displaystyle{ q }[/math] that intersects the maximum number of edges of [math]\displaystyle{ P }[/math].

In other words, if standing at point [math]\displaystyle{ q }[/math], in what direction should you aim a gun so the bullet will go through the largest number of walls. A bullet through a vertex of [math]\displaystyle{ P }[/math] gets credit for only one wall. An [math]\displaystyle{ O(n log n) }[/math] algorithm is possible.

Lower Bounds

4.39. In one of my research papers [Ski88], I discovered a comparison-based sorting algorithm that runs in [math]\displaystyle{ O(n log(\sqrt n)) }[/math]. Given the existence of an [math]\displaystyle{ \Omega(n log n) }[/math] lower bound for sorting, how can this be possible?

Solution

4.40. Mr. B. C. Dull claims to have developed a new data structure for priority queues that supports the operations Insert, Maximum, and Extract-Max—all in [math]\displaystyle{ O(1) }[/math] worst-case time. Prove that he is mistaken. (Hint: the argument does not involve a lot of gory details—just think about what this would imply about the [math]\displaystyle{ \Omega (n log n) }[/math] lower bound for sorting.)

Searching

4.41. A company database consists of 10,000 sorted names, 40% of whom are known as good customers and who together account for 60% of the accesses to the database. There are two data structure options to consider for representing the database:

• Put all the names in a single array and use binary search.

• Put the good customers in one array and the rest of them in a second array. Only if we do not find the query name on a binary search of the first array do we do a binary search of the second array.

Demonstrate which option gives better expected performance. Does this change if linear search on an unsorted array is used instead of binary search for both options?

Solution

4.42. A Ramanujan number can be written two different ways as the sum of two cubes—meaning there exist distinct positive integers [math]\displaystyle{ a, b, c }[/math], and [math]\displaystyle{ d }[/math] such that [math]\displaystyle{ a^3 + b^3 = c^3 + d^3 }[/math]. For example, 1729 is a Ramanujan number because [math]\displaystyle{ 1729 = 1^3 + 12^3 = 9^3 + 10^3 }[/math].

(a) Give an efficient algorithm to test whether a given single integer [math]\displaystyle{ n }[/math] is a Ramanujan number, with an analysis of the algorithm’s complexity.

(b) Now give an efficient algorithm to generate all the Ramanujan numbers between 1 and [math]\displaystyle{ n }[/math], with an analysis of its complexity.

Implementaion Challenges

4.43. Consider an n×n array [math]\displaystyle{ A }[/math] containing integer elements (positive, negative, and zero). Assume that the elements in each row of [math]\displaystyle{ A }[/math] are in strictly increasing order, and the elements of each column of [math]\displaystyle{ A }[/math] are in strictly decreasing order. (Hence there cannot be two zeros in the same row or the same column.) Describe an efficient algorithm that counts the number of occurrences of the element 0 in [math]\displaystyle{ A }[/math]. Analyze its running time.

Solution

4.44. Implement versions of several different sorting algorithms, such as selection sort, insertion sort, heapsort, mergesort, and quicksort. Conduct experiments to assess the relative performance of these algorithms in a simple application that reads a large text file and reports exactly one instance of each word that appears within it. This application can be efficiently implemented by sorting all the words that occur in the text and then passing through the sorted sequence to identify one instance of each distinct word. Write a brief report with your conclusions.

4.45. Implement an external sort, which uses intermediate files to sort files bigger than main memory. Mergesort is a good algorithm to base such an implementation on. Test your program both on files with small records and on files with large records.

Solution

4.46. Design and implement a parallel sorting algorithm that distributes data across several processors. An appropriate variation of mergesort is a likely candidate. Measure the speedup of this algorithm as the number of processors increases. Then compare the execution time to that of a purely sequential mergesort implementation. What are your experiences?

Interview Problems

4.47. If you are given a million integers to sort, what algorithm would you use to sort them? How much time and memory would that consume?

Solution

4.48. Describe advantages and disadvantages of the most popular sorting algorithms.

4.49. Implement an algorithm that takes an input array and returns only the unique elements in it.

Solution

4.50. You have a computer with only 4 GB of main memory. How do you use it to sort a large file of 500 GB that is on disk?

4.51. Design a stack that supports push, pop, and retrieving the minimum element in constant time.

Solution

4.52. Given a search string of three words, find the smallest snippet of the document that contains all three of the search words—that is, the snippet with the smallest number of words in it. You are given the index positions where these words occur in the document, such as word1: [math]\displaystyle{ (1, 4, 5) }[/math], word2: [math]\displaystyle{ (3, 9, 10) }[/math], and word3: [math]\displaystyle{ (2, 6, 15) }[/math]. Each of the lists are in sorted order, as above.

4.53. You are given twelve coins. One of them is heavier or lighter than the rest. Identify this coin in just three weighings with a balance scale.

Solution

Back to Chapter List