# Chapter 4

Revision as of 15:28, 18 September 2020 by Algowikiadmin (talk | contribs) (→Applications of Sorting: Numbers)

## Contents

# Sorting

### Applications of Sorting: Numbers

- 4.1. The Grinch is given the job of partitioning players into two teams of 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 time.

- 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, , 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
- (a) Let be an
*unsorted*array of integers. Give an algorithm that finds the pair that*maximizes*. Your algorithm must run in worst-case time. - (b) Let be a
*sorted*array of integers. Give an algorithm that finds the pair that*maximizes*. Your algorithm must run in worst-case time. - (c) Let be an
*unsorted*array of integers. Give an algorithm that finds the pair that*minimizes*, for . Your algorithm must run in worst-case time. - (d) Let be a
*sorted*array of integers. Give an algorithm that finds the pair that*minimizes*, for . Your algorithm must run in worst-case time.

- 4.3. Take a list of real numbers as input. Design an algorithm that partitions the numbers into 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 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 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

### Applicatoins of Sorting: Intervals and Sets

- 4.12

- 4.14

- 4.16

### Heaps

- 4.18

- 4.20

### Quicksort

- 4.22

- 4.24

- 4.26

### Mergesort

- 4.28

- 4.30

### Other Sorting Alogrithims

- 4.32

- 4.34

- 4.36

- 4.38

### Lower Bounds

- 4.40

### Searching

- 4.42

### Implementaion Challenges

- 4.44

- 4.46

### Interview Problems

- 4.48

- 4.50

- 4.52

Back to Chapter List