Counting each arithmetic calculation or comparison, extraction or exchange of a
ID: 2921420 • Letter: C
Question
Counting each arithmetic calculation or comparison, extraction or exchange of a card as one operation, what is the worst-case order of growth of an algorithm that sorts numbered cards in the following way?
1. Find the largest valued card in the deck by shuffling through one card at a time extracting a card if it is the largest one seen so far, and swapping the previously largest card back into the deck. When the largest has been found, place this card face down in a new pile and repeat the previous process until no cars in the original pile are left. Explain your answer.
2. This time we assume that the largest number on any of the n cards is n2. We sort the cards by placing a set of n2 plates numbered from 1 to n2 on a table. Then one by one, place each card on top of the numbered plate equal to it on the desk. The sorted list can be extracted by looking through the piles on all n2 plates in order.
3. This method can be improved to work in linear time. Explain how. Hint: This is not easy. Use division, to try turn each number into a pair of numbers, each with a value between 1 and n.
Explanation / Answer
1)
Each time we make a pass through the deck, we extract the largest card. Each pass through the deck takes O ( k ) time, where k is the number of cards remaining in the deck during that pass. The total number of times for all the passes is
( n + ( n - 1) + ( n - 2) + ( n - 3) + ... + 2 + 1) = (n(n+1)/2)
= ( n2 )
2)
To make the explanation clearer, we refer to the original cards we are trying to sort as cards , and will refer to the extra set of cards numbers 1 to n 2 that we place on the table as slots ; it is not important that they are cards, they are merely “placeholders”. It takes ( n 2 ) time to create the slots numbered 1 to n 2 on the table. We can then place the cards in their appropriate slot in a total time of ( n ). To obtain
the nal sorted list, we have to examine each of the n 2 slots, and pick up the cards in that slot (if any). It takes ( n2 ) time to examine the slots, and a total of ( n ) time to pick up the cards. The total time is therefore ( n 2 ), as above
Post Q3 again
Hint for Q3
We begin by creating slots numbered 1 to n on the table. We next divide each of our numbers by n , saving both the quotient and the remainder. Then, we place each number in the slot that corresponds to its remainder . We pick up the cards, starting from slot 1 and proceeding to slot n . At this point, we have the cards sorted in order of increasing remainder — cards that have the same remainder are in no particular order.