Problem Statement |
| | A "deque" is a data structure which allows constant time insertion and removal at both the front and back ends. In this problem, you will be given a int[] data, and asked to sort the numbers contained therein using the following algorithm. For each number x in data, you must do exactly one of the following:
- 1. Push x onto the front end of an existing deque.
- 2. Push x onto the back end of an existing deque.
- 3. Create a new deque with x as its only element.
You must process each number in data in the order they are given. It is not permissible to skip a number temporarily and process it at a later time. It is also not permissible to insert a number into the middle of an existing deque; only front and back insertions are allowed.
Once all the numbers have been processed, if you have created your deques wisely, you should be able to create a single, sorted list by placing the resulting deques on top of each other in an order of your choice. Your method should return the minimum number of deques needed for this to be possible. |
| |
Definition |
| | | Class: | HardDequeSort | | Method: | minDeques | | Parameters: | int[] | | Returns: | int | | Method signature: | int minDeques(int[] data) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | data will contain between 3 and 50 elements, inclusive. |
| - | Each element of data will be between -1000 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | {50, 45, 55, 60, 45, 65,
40, 70, 70, 35, 30, 75} |
| Returns: 1 | Only one deque is necessary to sort this list. The first element, 50, starts the deque. For each successive element encountered, if that element is less than 50, push it onto the front of the deque. Otherwise, if it is greater than 50, push it onto the back of the deque. Once all the data has been processed, the deque will contain all the elements and be in sorted order. |
|
|
| 1) | |
| | | Returns: 2 | Your algorithm could process the numbers in the following way:
- Create a new deque d1 = {3}.
- Create a new deque d2 = {6}.
- Push 0 onto the front of d1; d1 = {0, 3}
- Push 9 onto the back of d2; d2 = {6, 9}
- Push 6 onto the front of d2; d2 = {6, 6, 9}
- Push 3 onto the front of d2; d2 = {3, 6, 6, 9}
We can now combine the deques together by putting d2 after d1, resulting in the sorted list {0, 3, 3, 6, 6, 9}. Two deques were used (and it is impossible to succeed using any less than two), so the method returns 2. |
|
|
| 2) | |
| | {0, 2, 1, 4, 3, 6, 5, 8, 7, 9} |
| Returns: 5 | The five deques will be {0,1}, {2,3}, {4,5}, {6,7}, and {8,9}. It is impossible to use fewer than five deques and still be able to combine them into a single, sorted list at the end. |
|
|
| 3) | |
| | {454,537,7,976,537,908,976,908,-94,454,908,64,454,-731,908,-646,537} |
| Returns: 4 | |
|