54 lines
1.1 KiB
D
54 lines
1.1 KiB
D
import std.stdio;
|
|
import std.algorithm;
|
|
import std.random;
|
|
import std.range;
|
|
|
|
int pancake(int n) {
|
|
int gap = 2, sum = 2, adj = -1;
|
|
|
|
while (sum < n) {
|
|
adj++;
|
|
gap = 2 * gap - 1;
|
|
sum += gap;
|
|
}
|
|
|
|
return n + adj;
|
|
}
|
|
|
|
Range pancakeSort(Range)(Range r) {
|
|
foreach_reverse (immutable i; 2 .. r.length + 1) {
|
|
immutable maxIndex = i - r[0 .. i].minPos!q{a > b}.length;
|
|
|
|
if (maxIndex + 1 != i) {
|
|
if (maxIndex != 0) {
|
|
r[0 .. maxIndex + 1].reverse();
|
|
}
|
|
|
|
r[0 .. i].reverse();
|
|
}
|
|
}
|
|
|
|
return r;
|
|
}
|
|
|
|
void main() {
|
|
writeln("\nThe maximum number of flips to sort a given number of elements is:\n");
|
|
|
|
foreach (i; 1..11)
|
|
{
|
|
auto data = iota(1, i+1).array;
|
|
|
|
if (i != 1) {
|
|
// Protection against the edge case data.lenght == 1 not handled by randomShuffle
|
|
// where also data is invariant with regard to pancakeSort
|
|
do
|
|
data.randomShuffle;
|
|
while (data.isSorted);
|
|
}
|
|
|
|
auto sortedData = data.dup;
|
|
sortedData.pancakeSort;
|
|
|
|
writefln("pancake(%2d) = %2d e.g %s -> %s", i, pancake(i), data, sortedData);
|
|
}
|
|
}
|