www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Permutation Sort Algorithm Very Slow

reply "Agora" <goren.ali yandex.com> writes:
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 :)
Jun 07 2014
parent reply "Chris Cain" <zshazz gmail.com> writes:
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).
Jun 07 2014
parent reply "Ali GOREN" <goren.ali yandex.com> writes:
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).
Jun 07 2014
next sibling parent reply "Chris Cain" <zshazz gmail.com> writes:
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 :)
Jun 07 2014
parent "Ali GOREN" <goren.ali yandex.com> writes:
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 :)
Jun 07 2014
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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; }
Jun 08 2014
next sibling parent "JR" <zorael gmail.com> writes:
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
Jun 08 2014
prev sibling parent "Ali GOREN" <goren.ali yandex.com> writes:
 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
Jun 08 2014