Counting each arithmetic calculation or comparison, extraction or exchange of a
ID: 3591561 • 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.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.
2.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
Solution:
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 mere “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 sorted in order of increasing remainder — cards that have the same remainder are in no particular order.
Please, please upvote and ask your doubts in the comments.