Hi.

I've found some code

import std.stdio, std.algorithm;

void permutationSort(T)(T[] items) pure nothrow {
    while (items.nextPermutation) {}
}

void main() {
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
    data.permutationSort;
    data.writeln;

}

This code is running very slow

Runtime Seconds: 5-6

Why is running slow?

Sorry for my bad english :( :)

Thank you :)

On Saturday, 7 June 2014 at 21:40:08 UTC, Agora wrote:
> Why is running slow?

One of the main reasons is because the number of permutations an array has is n!. Thus the expected runtime is O(n!). That's a slow, slow algorithm in general. In particular, your array with length 11 has 39,916,800 permutations (although it, obviously, doesn't have to go through *all* of those to get the sorted sequence in this case).

Thank you. I can not resolve it in quicker time, right?

Also:

dlang online compiler and dpaste:

return code: 9 killed

why?

thank you

On Saturday, 7 June 2014 at 21:57:31 UTC, Chris Cain wrote:
> On Saturday, 7 June 2014 at 21:40:08 UTC, Agora wrote:
>> Why is running slow?
>
> One of the main reasons is because the number of permutations an array has is n!. Thus the expected runtime is O(n!). That's a slow, slow algorithm in general. In particular, your array with length 11 has 39,916,800 permutations (although it, obviously, doesn't have to go through *all* of those to get the sorted sequence in this case).

On Saturday, 7 June 2014 at 22:01:25 UTC, Ali GOREN wrote:
> Thank you. I can not resolve it in quicker time, right?

You might be able to come up with a faster way to permute, but it's mostly pointless because it will always be very slow. Use std.algorithm.sort if you want to sort quickly, as that uses an algorithm that is O(n log n)

Compare:
11! = 39,916,800
11 log_2 11 = ~38

So the best you could really expect to do is be around a million times slower than a regular sort.

>
> Also:
>
> dlang online compiler and dpaste:
>
> return code: 9 killed
>
> why?

Probably because it took too long. There's probably a pretty short timelimit on the execution of your program in the online things because they are shared resources.

> thank you

No problem :)

Thank you Chris. Now I understand. I thought myself incorrectly but this was a normal.

On Saturday, 7 June 2014 at 22:09:11 UTC, Chris Cain wrote:
> On Saturday, 7 June 2014 at 22:01:25 UTC, Ali GOREN wrote:
>> Thank you. I can not resolve it in quicker time, right?
>
> You might be able to come up with a faster way to permute, but it's mostly pointless because it will always be very slow. Use std.algorithm.sort if you want to sort quickly, as that uses an algorithm that is O(n log n)
>
> Compare:
> 11! = 39,916,800
> 11 log_2 11 = ~38
>
> So the best you could really expect to do is be around a million times slower than a regular sort.
>
>>
>> Also:
>>
>> dlang online compiler and dpaste:
>>
>> return code: 9 killed
>>
>> why?
>
> Probably because it took too long. There's probably a pretty short timelimit on the execution of your program in the online things because they are shared resources.
>
>> thank you
>
> No problem :)

On Saturday, 7 June 2014 at 22:01:25 UTC, Ali GOREN wrote:
> Thank you. I can not resolve it in quicker time, right?

Depends what exactly you want to achieve. This will achieve the same result in a fraction of the time.

void main() {
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
    sort(data);
    data.writeln;
}

But it's not "permutation sort". Honestly, I've never *heard* of "permutation sort". In any case, it's one of the worst sorts I've ever heard of.

If you want to use a bad algorithm, you could also go for bogosort:

void main() {
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
    while (!isSorted(data))
        randomShuffle(data);
    data.writeln;
}

On Sunday, 8 June 2014 at 08:44:42 UTC, monarch_dodra wrote: of.
> If you want to use a bad algorithm, you could also go for bogosort:
>
> void main() {
>     auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
>     while (!isSorted(data))
>         randomShuffle(data);
>     data.writeln;
> }

I'm partial to MiracleSort[1] myself.

void main() {
    import core.thread;
    immutable period = 1.seconds;
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];

    while (!isSorted(data)) {
        Thread.sleep(period);
    }

    data.writeln();
}


[1]: http://stackoverflow.com/questions/2609857/are-there-any-worse-sorting-algorithms-than-bogosort-a-k-a-monkey-sort/6947808#6947808

@monoarch_dodra

I solved BogoSort

import std.stdio, std.algorithm, std.random;

void bogoSort(T)(T[] data) {
    while (!isSorted(data))
        randomShuffle(data);
}

void main() {
    auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8];
    bogoSort(array);
    writeln(array);
}

https://github.com/agoren/AlgorithmSolved/blob/master/BogoSort/main.d