Sorting Numbers

Computer Science Level 1

Alice has 9 numbers and wants to sort them in increasing order: $7, 8, 2, 9, 5, 1, 8, 5, 3.$ It should be an easy task, but Alice only knows how to sort 6 numbers! Therefore, she does the following:

Sort the first 6 numbers to get ${\color{#D61F06}1, 2, 5, 7, 8, 9}, 8, 5, 3.$
Sort the last 6 numbers to get $1, 2, 5, {\color{#D61F06}3, 5, 7, 8, 8, 9}.$
Sort the first 6 numbers again to get ${\color{#D61F06}1, 2, 3, 5, 5, 7}, 8, 8, 9.$

Finally, it sorts the 9 numbers! Does this method work for any 9 numbers?

Yes, always No, only sometimes

3 solutions

Michael N.
Nov 14, 2017

After sorting the first three numbers, it is true that the forth, fifth, and sixth numbers will each be greater than the first three, meaning that none of the three greatest numbers are in the first three positions. After the second sort, it is true that the last three numbers will be the greatest of the nine, as the second sort deals with all numbers but the first three, which are guaranteed to not be a part of the greatest three. The final sort deals with the first six numbers, which are also the lowest six. After the final sort, the first and lowest six are sorted in increasing order, and the remaining, last, and greatest three numbers are sorted in increasing order. This meaning that all nine numbers are sorted in increasing order.

Andrei Stephenson
Nov 18, 2017

There are 3 cases to consider: 1. Sorted list 2. Reverse sorted list 3. Unsorted list Notation: Upper Group: Last 6 numbers taken together Lower Group: First 6 numbers For case 1 Alice's method will solve it in 3 steps but not positions will be swapped. For case 2, without going into any maths, will see the largest 6 numbers at the front in the lower group being reversed in the first step. The second step will reverse the upper group placing the smallest numbers at the front and the largest numbers at the end. The third step will align the middle numbers that form the overlap between the upper and lower groups. For case 3 we'll need to do a bit of math. Let us represent the 9 numbers as a1, a2, ..., a9. Now the number of possible combinations of a1 - a9 is 9! or 362880. We can ignore case 1 and 2 so subtracting these cases we have 362878 combinations. From case 2 we can ascertain what happens in each step which will indicate what happens to the remaining cases. Step 1 pushes the largest number to the end of the lower group and the smallest number to the beginning. Step 2 does the same for the upper group, so at this stage the last 3 numbers are in their correct positions. Step 3 sorts the 3 numbers that formed the overlap in both groups thus sorting the entire list as a whole.

Hwa Rang Kim
Nov 17, 2017

To make things simple, we will keep track on number 7,8,9 after the first step, number 7,8,9 are guaranteed to be in the last 6 seats. so, after the second step they would be on their place( 7 on 7th, and so on.) that would leave 1 to 6 on the first 6 seats. PROBLEM SOLVED

Sorting Numbers

3 solutions

0 pending reports