8
$\begingroup$

I have a physical stack of cards, with numbers on them (or, in reality, I have a stack of exams, with students names on them ;)). I want to sort the cards in ascending order.

This is an extremely boring task. I usually use mergesort myself (quick question: what do you use?). But say each card has a QR code. I can scan all the codes as I go through the stack using my mobile phone and then I have the list of cards and the order in which they appear.

What would be a clever way to use this information in order to tell a human how to sort the stack of cards? I imagine that the computer could somehow give me instructions of what to do so as to arrive at the sorted order. Notice that things like "take the 52nd card and place it on the top" are not nice, since I don't want to count to the 52nd card. What would you do?

I realize this question is rather subjective: what constitutes a "nice" strategy depends on the person. I just want to know what kinds of ideas you people could come up with.

Improve this question
$\endgroup$
3
  • $\begingroup$ As you have noticed it is quite subjective task, which does not fit well to Q&A format. But let me assume you will edit the question to make it more fitting - what operations are ok? If you do not have access to $i-th$ paper, and probably you are interested in spending least time - making access hard grows in number of swaps - not very efficient tradeoff. So please define your objective. $\endgroup$
    – Evil
    Commented Jul 8, 2016 at 23:30
  • $\begingroup$ And quick answer - ask people to put papers in order of points gathered - quite good estimator. But this "strategy" fits more to chat, not as subquestion. $\endgroup$
    – Evil
    Commented Jul 8, 2016 at 23:33
  • 1
    $\begingroup$ It's a mostly ignored question - what is the fastest way to sort n items if the cost of moving an item is substantially higher than the cost of comparing two items? As an example, quicksort can be adapted by using a pivot that is not close to the median to reduce the number of moves at the cost of more comparisons. $\endgroup$
    – gnasher729
    Commented Jul 9, 2016 at 12:14

1 Answer 1

Reset to default
7
$\begingroup$
  1. Setup an array of initially empty file folders (even better buy a mail sorter and you are in the pigeonhole sort case).
  2. The computer, knowing the initial order of the cards, will tell you, one by one, where to put each card (you have a limited number of folders so instructions like "take the current card and place it on top / bottom of folder 3" are quite easy to follow).
  3. Manually sort each non empty folder using insertion-sort.
  4. Visit the folders in order and put all cards back onto the table.

(repeat n times and you're ready for the parcel delivery office, almost... a railway post clerk was required to sort 600 pieces of mail in an hour with 97% accuracy in order to keep his job :-)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think this is a good solution (a kind of bucket sort), though I haven't tried it yet. Actually, the whole QR code idea is not really necessary in a small application: if you know beforehand the numbers on the cards (or names of students), then you can precompute a good distribution of which cards go into which buckets. $\endgroup$
    – Fernando
    Commented Jul 9, 2016 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.