3. Exercise 3.14 of the textbook A card game program keeps a deck of cards in an

Question

3. Exercise 3.14 of the textbook

A card game program keeps a deck of cards in an array. Give an algorithm to "unshuffle" the deck so that all the cards of a suit are grouped together, and within each suit, the cards are in ascending order or rank--consider the ace as the lowest ranked card. Since there are only 52 cards, space is not an issue so you can use extra space if needed. The only constraint is that your algorithm be as fast as possible.

What is the worst case big O running time of your algorithm? What are the basic operations you used in your analysis? Is the average big O running time different from the worst case?

Explanation / Answer

Below is the algorithm for the problem: -

1. Allocate four new arrays, each of length 13, one for each suit.

2. Go through the original deck from front toend, and slot each card in its appropriate position in the suit array to which it belongs. So for example thequeen of hearts will go to index position 11 in the hearts array.

3. Note that since the indexes of the arraysare from 0 through 12, the array position of a card will be one less than its face value. (Queen's face valueis 12, so its array position will be 11.)

The big O running time is O(1)!!

The basic operations are (a) looking up a card in the deck array, and (b) writing it into a suit array. Each ofthese takes unit time. (Writing takes unit time because the suit array is directly indexed with the card'sface value.) Since there are 52 look ups and 52 writes, the total number of basic operations, and thereforethe total units of time, is 104. This is a constant, so the big O time is O(1).

Because big O is constant i.e. worst case time is in terms of O(1), its average case time will also be same.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.