http://qs321.pair.com?node_id=144516


in reply to sort with fewest moves

The way i'm reading your post is: "I'm looking for an algorithm that will let me sort elements 1-N, given that the only memory available is an array from 1-N, plus a single temp variable, and the only allowed opperation is  move(n, m)".

This sounds alot like Bubble Sort to me.

The distinction being that Bubble Sort is usually defined in terms of a  swap(a, b) method which is considered atomic. Since  swap) can be (and frequently is) defined in terms of two moves that use a temp variable, Bubble Sort can solve your problem given your constraints -- uut it will never come close to a solution with a minimal number of moves. It will only ever call  move(a, 0) and  move(0, a).

I can't think of any other constant space sorting algorithms (that operate on arrays). But one extremely important question that needs to be answered before you can even try to for finding an optimal algorithm is: how do you define optimal? is move(n,m) the only operation with a "cost" ? what about doing comparispons or slots? Would a solution that analyzed all of the slots in detail first,then built up a list of moves be considered optimal?

(I ask, because you're post only refers to the ideal situation being one in which "the number of moves is minimal.")

Replies are listed 'Best First'.
Re: Re: sort with fewest moves
by theorbtwo (Prior) on Feb 10, 2002 at 22:59 UTC

    In this case, it appears that yes, move(n,m) is the only operation with cost. (I'm not sure if it's cost is constant over all n,m. I think we're supposted to assume that it is.)

    In purticular, this is going to be applied to a tape-library servicing robot, which only has one operation: switch the tapes in positions N and M. (move(n,m))

    You're right about bubble-sort being a possiblity... but I don't think it's a good one. Remember that it isn't finding the sequence of moves that has to be done in constant space, it's the acautual movement of physical tapes.

    TACCTGTTTGAGTGTAACAATCATTCGCTCGGTGTATCCATCTTTG ACACAATGAATCTTTGACTCGAACAATCGTTCGGTCGCTCCGACGC
      That's why I'm not clear on the goal, is it:
      Find an algorithm, whose performance is inconsequential, that can determine the minimal number of moves to sort the tapes.
      Or is it something like:
      Find an optimal algorithm for sorting the tapes such that the only atomic operations move(m,n) and examine(n) -- which tells you what tape is in slot n.

      If any amount of preprocessing and analysis is allowed, then any number of hueristics could be useful for find a path from the starting order to sorted order.

      If nothing else, you can do a breadth first search of all the possible permutations of moves untill you achieve the desired ordering.

Re: Re: sort with fewest moves
by axelrose (Scribe) on Feb 11, 2002 at 19:26 UTC
    > is move(n,m) the only operation with a "cost" ?

    Practically yes. Finding the right order is easily achieved with Perl in memory. The cost mainly results from time a robot arm needs to pick and move a tape. (about 30 seconds)

    I neglect the time difference for tape moves betwenn different slots. (a maximum of 60 tapes)

    > Would a solution that analyzed all of the slots in detail first,then built up a list of moves be considered optimal?
    Yes - that's how I want to solve it.