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.6

4.8

4.10