CODEWITHSUNDEEP
sorting
user433342
user433342

Reputation: 1050

Sort a move to end list

A sequential unique list of numbers (1,2,3,...,n) has been randomized and I need to sort it by moving one item at a time to the end of the list. Which algorithm will provide the least number of moves?

Note: [123645] can be sorted with 1 move, [125346] in 2 moves, [654321] will need 5 moves. I'd like an algorithm that can account for these, not one that just gives me n-1 all the time.

Best I can think of: 

for(var x=1; x<=list.length; x++)
if indexOf(x+1)<indexOf(x) then move x+1 to end

Does this work? Best solution?

Upvotes: 0

Views: 1262

Answers (2)

zord
zord

Reputation: 4783

Here is my second solution:

function mysort(array) {
    var index, value, badValues,
        len = array.length;
    // find values at a bad place
    badValues = [];
    for (index = 0; index < len; index++) {
        if (array[index] !== index + 1 - badValues.length) {
            badValues.push(array[index]);
        }
    }    
    // move those to the end in increasing order
    while (badValues.length > 0) {
        // minimum bad value
        value = Math.min.apply(null, badValues);
        index = array.indexOf(value);        
        // move to the end
        array.splice(index, 1);
        array.push(value);
        // one bad solved
        badValues.splice(badValues.indexOf(value), 1);    
    }
    return array;    
}

Here is a demo fiddle. As you can see, the input [1,2,9,3,4,8,5,6,7] is sorted by 2 moves, and a fully random, or reversed list is still n-1 moves.

Upvotes: 0

Ranveer
Ranveer

Reputation: 6871

Here's an algorithm:

  1. Check the length of the list (from the beginning) till which it is increasing, i.e., stop when the list starts to decrease.
  2. Subtract that length from the length of the list. And that is your answer.

Quite intuitive, just think about it. Example:

12345 -> 25341
|25| is in increasing order and after that it becomes decreasing.
Length (2,5) = 2
Answer = 5 - 2 = 3

If your list isn't sorted in increasing order, you could always map it via indices.

Upvotes: 1

Related Questions