# sorting stone Problem [closed]

My friend asked this problem recently & am not sure which sorting to use for this kind of problem:-

There are 20 stones of different heights. Each stone is so heavy, we need to sort the stones such that smallest stones are to left and highest to right. As stones are heavy make algorithm which moves stone least distance possible

Which sorting method suits this kind of problem?

• Grow some muscles and use mergesort! :-D – David Richerby Dec 3 '13 at 10:15
• Any Reason for using mergesort? @DavidRicherby – Hari Krishna Dec 3 '13 at 10:27
• I was just being silly. Mergesort isn't an in-place sort so you'd have to carry the stones around an awful lot. – David Richerby Dec 3 '13 at 13:06
• I tend to think any real stone sorting procedure where distance moved is the objective is going to be pretty different from sorting algorithms typically analyzed in CS. Distance moved isn't usually the objective in sorting algorithms for random access machines. Can you provide more details on the physics of this scenario? What are the dimensions of the stones? Can they move through each other? Can they move forward, backward, left, right, and up and down? Do distances in all six directions count towards the total distance? – Patrick87 Dec 6 '13 at 17:45

Original question.

Could Any one provide a better solution for this?

I didn't see any solution provided, so that is not a valid question. Just pointing out that we expect an effort to be made by you on solving your problem before we put in an effort to help you.

Revised question.

Which sorting method suits this kind of problem?

If I understand this correctly, it is not the choice of a sort algorithm that is important but getting the least number of moves that is important.

So first you can choose any sort method and find the correct order of the stones.

Now knowing the unsorted order and the sorted order, find the least number of moves. Since I will take it that there is a place off to the side that you can place one stone, it should take no more than a maximum of n+1 moves to sort all of the stones.

• Not a bad answer, but does it really address the question? The metric to minimize is distance moved, not number of moves. – Patrick87 Dec 6 '13 at 16:11
• If the number of moves is the minimum then how is that different from the minimum distance moved? I would agree that the first stone that is moved is moved twice, once into the temp place and then again at the end into the final place, but I can tweak the answer for that. – Guy Coder Dec 6 '13 at 17:00
• I can guess that the op is looking for a sort algorithm where each move requires a cost per distance value associated with it, but the op did not say that. If they do then it should be a new question and I hope if that is what the op wants then they ask a new question with that in the description as that is a different question. – Guy Coder Dec 6 '13 at 17:04
• It's not immediately clear to me that minimum number of moves is the same thing as minimum distance moved. For one, I can do many small moves and, provided they're all moving stones in the correct direction, it doesn't necessarily hurt the distance. Also, I think it's conceivable that minimum number of moves may sometimes work against minimum distance. Perhaps I'm reading too much into the question, but I'm assuming that the stones are such that you can't slide them through each other, and that they can only be moved around a plane. Fewer moves may mean longer moves, to avoid other stones. – Patrick87 Dec 6 '13 at 17:27
• I didn't confine the stone to a plane as I view them as real stones being moved by real people. For a move just pick up the stone, move it over or around a stone and place it in it's final place, expect for the first stone which needs to be moved twice. If I really wanted to cheat the question I would just have someone else move the stones then I would have a move count of zero. – Guy Coder Dec 6 '13 at 17:33

I'll be very interested to see a real answer for this. This is a tough problem.

I propose that we first figure out the sorted order, which we can do without touching the stones. Now, consider the worst case: the stones are in reverse-sorted order. The minimum distance required to move the stones to the correct positions is greater than $d(n-1) + d(n-2) + ... + d(n/2-1) + ... + d(n-2) + d(n-1)$ which is going to be $O(n^2)$ in the number of stones to sort. There is no sorting algorithm that will move stones such that the worst-case efficiency is any better than quadratic (under some assumptions, see below).

Given that, consider the dumbest algorithm imaginable:

1. Figure out the sorted order
2. Slide stones up, over, then up, one at a time, to put them in sorted order two squares above the original row.
3. Slide each stone down two squares.

Here, the horizontal sliding distance is optimal (assuming stones must return to the original row; if this is not actually required, the problem becomes significantly more interesting). We pay a tax of 4 moves per stone, $O(n)$ overhead, which is eaten by the $O(n^2)$ term in the worst case. The extra distance for moving vertically is $8rn$, or $80$ squares for the $n=20$ case, where the minimal distance in the worst case is at least about $380$. The number of squares would be $4000$ for the $n=1000$ case, where the minimal distance in the worst case is about $999,000$.

It seems likely that any workable algorithm (that returns stones to the original row, at least) is going to need to pay a tax of at least $\pi r - 2r$, or about $1.14r$, for round stones of cross-sectional radius $r$ that can rotate around each other, or $s$ for square stones of cross-sectional side $s$ that slide around each other on a grid.

There are some heuristics you can use to make the runtimes better in some cases, but I doubt whether there's a method to get around the $O(n^2)$ required for horizontal distances (unless we're allowed to line the stones up somewhere else, in which case this becomes more challenging).

(If the question is about finding a real procedure that gets the vertical move tax down as close to optimal as possible, that's something we can also discuss, but it will be useful to frame the question in those terms if that's the case. Even the dumb algorithm above can be modified so that in cases other than the worst, performance is significantly better).