4

Here is a problem I'm trying to solve for a personal project. I'm not exactly sure how best to even approach it.

Problem:

I have a single stack already populated with several thousands of unknown items. (Not completely unique items, maybe 300 different values. So it's a stack with plenty of duplicates shuffled together in a random order.) I want to sort these items by moving them between a limited number of other stacks. (Maybe between 10-30 stacks at most.) An algorithm with less moves is ideal.

Limitations:

  • The initial stack is full of unknown values (except for the top item).
  • I can read the top item in a stack.
  • I can move the top item of a stack directly to the top of another stack.
  • I can check if a stack is empty.
  • I can remember and store all the items I have read and moved.

Based on the above limitations, all the items need to be moved once to another stack just so they can be read/scanned. Then I would know where and what everything is.

Once this is done I can do the real sorting. (This is the part I mainly need help with.) After I've read and moved all the items once, I can then calculate and queue up all the stack moves needed to actually sort the items.

Presorting and optimizing:

It might be too early to think about this, but I can potentially do some pre-sorting onto different stacks as the items are first read and moved.

I do have a overall idea about the distribution of all the items. For instance, if the items were sorted alphabetically, I might know that items values starting with "S" are five times more common then items that start with "V" and that "S" is also twice as common as items starting with "A". Is knowing this even useful here?

I'm not sure if this would be helpful for pre-sorting but in some instances I might also know all the possible values of the items. So I could calculate if the value of an item is "odd" or "even". Even other similar calculations can be done (like the remainder of a larger modulos operation). Maybe separating the items into "odd" or "even" stacks would make it easier to weave into the final sorted stacks. I'm just speculating here, since I haven't run any tests yet.

Desired Result:

Items don't need to be sorted back into a single stack, it would probably actually be more ideal if they were moved into several smaller stacks of somewhat equal size. For example, I might end with alphabetically sorted stacks as such: A-D, D-K, K-R, R-S, S-Z.

What kind of algorithms would be best given these limitations? Pseudo code?

  • 3
    can you describe your actual problem and use-case? they way you describe it, it sound like you should use Linked-Lists instead of proper stacks, and then just sort the lists. Maybe a simple merge-sort? or even a radix or bucket sort.... – AK_ May 2 '15 at 10:10
  • Aside from the initial stack which is more of a black box, I think you are right, I probably do want to store everything else in lists, so I can remember the placement of everything. However I'm still stuck with the above limitations for the operations on how I'm allowed to sort the lists, as they are physical limitations. – Daichi May 2 '15 at 15:39
  • It seems you're solving en.wikipedia.org/wiki/Tower_of_Hanoi – r.pankevicius May 3 '15 at 20:04
  • Reminds me of game Solitaire. Could you use algorithm from there by any chance? – Alexus Jul 2 '15 at 22:45
  • Solitaire, that is an interesting way of looking at this. I kinda put this on the back burner, but I'll give that some thought when I get back to it. – Daichi Jul 7 '15 at 6:30
1

Do a "binning" of the initial black box stack into N groups of equal proportions (your A-D, D-K...). At that point you can use any O(n log n) algorithm to sort each group in turn.

Actually, you could pop items from the black-box stack directly into a group of N red-black trees.

But if you have lots of identical elements... could you not just store a counter into a single tree? If you only have 300 values, you might then store your several thousands values into a single tree of comparatively small height. When extracting values you'd just decrement the counter and delete the element when the counter eventually reached 0. And you could use the tree to fill the output stacks if you found that you still needed them.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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