Sorting permutation efficiently

Question

Given an unsorted permutation of [n], I want to collect the numbers by iterating from left to right in order to sort the premutation (1...n).
What is the number of iteration I have to do in order to acheieve this goal?
For example:
Given '3, 7, 4, 2, 10, 8, 9, 1, 6, 5'- the number of iterations is 6.
In the first iteration I will collect the number 1
In the second iteration I will collect the number 2
In the third iteration I will collect the numbers 3,4,5
In the forth iteration I will collect the number 6
In the fifth iteration I will collect the numbers 7,8,9
In the sixth iteration I will collect the number 10

I build a naive code, doing the task with O(n^2), but I need it to be more efficient, so I think there's a trick I'm missing here.
Any suggestions?

Answer 1

I tried to implement your sample in PERL.

#!/usr/bin/perl
if ($#ARGV < 0) {   # with no arguments
    @data = (3, 7, 4, 2, 10, 8, 9, 1, 6, 5);
}
else {
    @tmp = (1..$ARGV[0]);
    while(@tmp) {
        push(@data, splice(@tmp, rand($#tmp), 1));
    }
}
$key = 1;
while (@data) {
    @remove = (); @remain = ();
    printf "key = $key\t(@data) --> ";
    foreach $i (@data) {
        if ($i == $key) {   # found
            push(@remove, $i);
            $key++;
        }
        else {
            push(@remain, $i);
        }
    }
    @data = @remain;
    print "(@remove) & (@data)\n";
    $count++;
}
print "Iteration = $count\n";

As a result.

$ ./a.pl  
key = 1 (3 7 4 2 10 8 9 1 6 5) --> (1) & (3 7 4 2 10 8 9 6 5)
key = 2 (3 7 4 2 10 8 9 6 5) --> (2) & (3 7 4 10 8 9 6 5)
key = 3 (3 7 4 10 8 9 6 5) --> (3 4 5) & (7 10 8 9 6)
key = 6 (7 10 8 9 6) --> (6) & (7 10 8 9)
key = 7 (7 10 8 9) --> (7 8 9) & (10)
key = 10    (10) --> (10) & ()
Iteration = 6
$ ./a.pl  10
key = 1 (2 1 4 8 5 9 3 6 7 10) --> (1) & (2 4 8 5 9 3 6 7 10)
key = 2 (2 4 8 5 9 3 6 7 10) --> (2 3) & (4 8 5 9 6 7 10)
key = 4 (4 8 5 9 6 7 10) --> (4 5 6 7) & (8 9 10)
key = 8 (8 9 10) --> (8 9 10) & ()
Iteration = 4
$ ./a.pl  10
key = 1 (3 1 7 8 6 2 9 5 4 10) --> (1 2) & (3 7 8 6 9 5 4 10)
key = 3 (3 7 8 6 9 5 4 10) --> (3 4) & (7 8 6 9 5 10)
key = 5 (7 8 6 9 5 10) --> (5) & (7 8 6 9 10)
key = 6 (7 8 6 9 10) --> (6) & (7 8 9 10)
key = 7 (7 8 9 10) --> (7 8 9 10) & ()
Iteration = 5

Answer 2

If you know that in assumption is given an array where for sure are present all elements of the permutation of [n] then I think:

1. Allocate an array y[1..n]

2. In one loop from 1 to n search initial array x of unsorted elements colecting items in each iteration the following way: y[x[i]] := x[i]

3. After the loop all in y is a sorted permutation with O (n)

-- edited 20-12-2014 22:54 CET:

The solution above works only for situation, where there is n-elementh table of integers from 1 to n unordered in any given way.

I'd like to explain in details how you can achieve the goal with only one iteration through the inpput array basing on your example.

Let's take the initial array:

x[] = { 3, 7, 4, 2, 10, 8, 9, 1, 6, 5 }

As a result let's take the following array filled at start with zero's:

y[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

Now let each item of the following ordered list be an iteration of the sorting algorithm:

1. We take x[1] which equals 3 - let's write it under 3rd position in result table y:

   y[3] := 3 (which in fact is: y[x[1]] := x[1])

   the result table now looks like following

   y[] = { 0, 0, 3, 0, 0, 0, 0, 0, 0, 0 }

2. In second step we take x[2] which equals 7 and we repeat the steps:

   y[7] := 7 (which in fact is: y[x[2]] := x[2])

   the result table now looks like following

   y[] = { 0, 0, 3, 0, 0, 0, 7, 0, 0, 0 }

3. Third step: x[3] which equals 4:

   y[4] := 4 (which in fact is: y[x[3]] := x[3])

   result table:

   y[] = { 0, 0, 3, 4, 0, 0, 7, 0, 0, 0 }

4. x[4] which equals 2:

   y[2] := 2 (which in fact is: y[x[4]] := x[4])

   result table:

   y[] = { 0, 2, 3, 4, 0, 0, 7, 0, 0, 0 }

5. x[5] which equals 10:

   y[10] := 10 (which in fact is: y[x[5]] := x[5])

   result table:

   y[] = { 0, 2, 3, 4, 0, 0, 7, 0, 0, 10 }

6. x[6] which equals 8:

   y[8] := 8 (which in fact is: y[x[6]] := x[6])

   result table:

   y[] = { 0, 2, 3, 4, 0, 0, 7, 8, 0, 10 }

7. x[7] which equals 9:

   y[9] := 9 (which in fact is: y[x[7]] := x[7])

   result table:

   y[] = { 0, 2, 3, 4, 0, 0, 7, 8, 9, 10 }

8. x[8] which equals 1:

   y[1] := 1 (which in fact is: y[x[8]] := x[8])

   result table:

   y[] = { 1, 2, 3, 4, 0, 0, 7, 8, 9, 10 }

9. x[9] which equals 6:

   y[6] := 6 (which in fact is: y[x[9]] := x[9])

   result table:

   y[] = { 1, 2, 3, 4, 0, 6, 7, 8, 9, 10 }

10. The last iteration:

    x[10] which equals 5:

    y[5] := 5 (which in fact is: y[x[10]] := x[10])

    result table:

    y[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

As we can see table y is a fully sorted version of input table x that was generated with 10 iterations (so O(n) cost level). No matter how big is n and how much unordered is the given input table, with those particular assumptions taken, the cost is constant and equals n;

I hope I didn't misunderstood your question.

Answer 3

Invert the permutation, then count how many times two consecutive numbers are decreasing, plus one.

def iterations(perm):
    invperm = [None] * len(perm)
    for i in range(len(perm)):  # yes, we could use enumerate
        invperm[perm[i] - 1] = i
    count = 1
    for i in range(1, len(perm)):
        count += invperm[i - 1] > invperm[i]
    return count

Explaination:

     Given          : 3, 7, 4, 2, 10, 8, 9, 1, 6, 5

                 x  : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Index of x in the given array : |8, |4, |1, 3, 10, |9, |2, 6, 7, |5

If indexes are out of order then you have to start again. So if you count |s then you know number of iterations you need.

Answer 4

Since you already know the result, it's unclear to me in what sense you're "sorting" anything. What result are you looking for -- the information about what numbers are "collected" at each iteration, as you show in your Q? In this case here's a simple Python 2 implementation example:

target = 3, 7, 4, 2, 10, 8, 9, 1, 6, 5

def do_permut(targ):
    look_for = 1
    iter_num = 1
    while look_for != len(targ) + 1:
        print 'Iteration', iter_num, ':',
        for item in targ:
            if item == look_for:
                print item,
                look_for += 1
        print
        iter_num += 1

do_permut(target)

However the task is inevitably O(N squared) -- remember big-O stands for worst case! You'll have up to N iterations (worst case realized when targ is reverse sorted to start with) each over N numbers -- thus, N squared. You could slightly optimize each iteration by collecting a set of numbers previously seen during it and breaking when look_for is in that set, but that only (roughly) halves each iteration's work, so it's still O(N squared).

If you can explain better what results and outputs you expect from your work we may be able to help more!

Just for curiosity here's a version with the above "improvement" and also a sanity check to ensure it raises an exception, rather than looping forever, if passed a sequence that's NOT a permutation of [1:n)...:

target = 3, 7, 4, 2, 10, 8, 9, 1, 6, 5

def do_permut(targ):
    look_for = 1
    iter_num = 1
    while look_for != len(targ) + 1:
        print 'iteration', iter_num, ':',
        seen = set()
        found_in_iter = 0
        for item in targ:
            seen.add(item)
            if item == look_for:
                print item,
                found_in_iter += 1
                look_for += 1
                if look_for in seen:
                    break
        print
        if not found_in_iter:
            raise ValueError('missing: %s' % look_for)
        iter_num += 1

do_permut(target)