digitalmars.D.learn - Permutation Sort Algorithm Very Slow

• Agora (16/16) Jun 07 2014 Hi.
• Chris Cain (7/8) Jun 07 2014 One of the main reasons is because the number of permutations an
• Ali GOREN (7/15) Jun 07 2014 Thank you. I can not resolve it in quicker time, right?
• Chris Cain (14/20) Jun 07 2014 You might be able to come up with a faster way to permute, but
• Ali GOREN (3/27) Jun 07 2014 Thank you Chris. Now I understand. I thought myself incorrectly
• monarch_dodra (19/20) Jun 08 2014 Depends what exactly you want to achieve. This will achieve the
• JR (13/21) Jun 08 2014 I'm partial to MiracleSort[1] myself.
• Ali GOREN (13/13) Jun 08 2014 @monoarch_dodra
"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
"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
"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
"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
"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
"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
"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() {
immutable period = 1.seconds;
auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];

while (!isSorted(data)) {
}

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
"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