Algorithm: optimal way to rearrange a list from one order to another?

Question

EDIT: I'm not sure that my original question is clear enough. I need an algorithm that will compute the minimal sequence of moves to rearrange an array from one order to another. It is known that both arrays will contain the same elements (no duplicates) and have the same length. For example:

reorder(
  ['d', 'a', 'c', 'b', 'e'],
  ['a', 'b', 'c', 'd', 'e']
)

should return something like:

[
  {move:'d', after:'b'},
  {move:'c', after:'b'}
]

which indicates that I should first move the element 'd' to after 'b', then move 'c' to after 'b' and the array will be in the desired order.

---

Background: I'm working on a project (moving most of the functionality in rtgui to the client-side, actually). Right now I'm working on sorting. Basically I have a list of divs that I want sorted in some arbitrary order. I can get the desired order as follows:

var hashes = {
  before: [],
  after: [],
};
var els = $('div.interesting-class').toArray();
var len = els.length;

for(var i = 0; i < len; i++) hashes.before.push(els[i].id);
els.sort(getSortComparator());
for(var i = 0; i < len; i++) hashes.after.push(els[i].id);

Now hashes.before and hashes.after contain the unordered and ordered lists of element IDs. When reordering the list, the most expensive operation, by far, is actually moving the DOM elements around. I had been doing this as follows:

var c = $('#container-id');
$(els).each(function() {
  c.append(this);
});

This works, but is slower than necessary, since on average, only 2 or 3 elements really need to be moved. Therefore, I need an algorithm that will compute the minimal sequence of moves to rearrange an array from one order to another (in this case, operating on hashes.before and hashes.after). Can anyone suggest one or give any ideas?

I've tried several general-purpose "diff" algorithms so far, but they didn't really give me what I wanted. I think what I need is like that, but more specialized.

Answer 1

The obvious idea is algorithm is the parameter.

Answer 2

My first thought is you should use Selection sort instead of the built-in sort method, since it makes the lowest ammount of swaps needed. That way you can just move the DOM element around when moving the id in the list.

Answer 3

Split out the keys and the array indexes into a separate array of objects {key, index}. Sort that array (using the best sort you can, of course; either a merge sort if the comparisons are expensive, or quicksort if they're cheap). You now know, from the actual indexes into the sorted array and the index values stored in each element, how to rearrange the original array.

Once you've sorted the keys, the "optimal" number of moves will be the O(n) of the original array. If you want to rearrange the original array in place, then you can derive the interchanges from your sorted list of indexes pretty simply.

Answer 4

Knuth Volume 3 has a section on "sorting networks". He doesn't go into a lot of detail about how to construct minimum comparison networks, but does cite some work (e.g., by Batcher and himself) about how to construct them. Note that while these are notes as "minimum comparison networks", few (if any) of them has really been proven to be minimal -- they're attempts at minimizing the number of comparators needed, but not necessarily successful in terms of actually achieving the true minimum.

Answer 5

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Find the longest increasing subsequence (according to the new sort order). Then move each element which is not in that sequence, into its place relative to the elements already in the sequence.

In your example, 'a, b, e' and 'a, c, e' are tied for longest increasing subsequence. The best you can do is choose one of those, and just move the other elements.