元素的就地排序

Phobos是否有一些可变算法来对l值引用参数进行排序？像元素的就地排序

int a=3; 
int b=2; 
int c=1; 

orderInPlace(a,b,c); 

// a is now 1 
// b is now 2 
// c is now 3

而且功能性变异的东西，说order(a, b, c)，返回一个元组也将是不错。如果不是，我想我们应该使用std.algorithm:swap。请参阅http://forum.dlang.org/thread/[email protected]#post-eweortsmcmibppmvtriw:40forum.dlang.org。

来源

2014-01-13 Nordlöw

亚当的解决方案工作，虽然它使用的是元素的临时副本。随着small modification to std.algorithm，有可能写这种种就地元素的版本：

import std.algorithm; 
import std.stdio; 
import std.traits; 
import std.typecons; 

struct SortableRef(T) 
{ 
    private T * _p; 
    @property ref T value() { return *_p; } 
    alias value this; 
    void opAssign(T * value) { _p = value; } 
    @disable void opAssign(SortableRef!T value); 
    void proxySwap(SortableRef!T other) { swap(*_p, *other._p); } 
} 

template PointerTo(T) { alias T* PointerTo; } 
void orderInPlace(T...)(ref T values) 
    if (!is(CommonType!(staticMap!(PointerTo, T)) == void)) 
{ 
    alias CommonType!T E; 
    SortableRef!E[values.length] references; 
    foreach (i, ref v; values) 
     references[i] = &v; 
    references[].sort(); 
} 

void main() 
{ 
    int a=3; 
    int b=1; 
    int c=2; 
    orderInPlace(a, b, c); 
    writeln([a, b, c]); 
}

然而，这是唯一可行的，如果传递给orderInPlace的值大，无法分配，或以其他方式不切实际的复制。

来源

2014-01-14 00:30:43

这确实很聪明。谢谢。 –

也许您应该在github问题主题中添加对此重要答案的引用，以获取更多关于为什么std.algorithm pull请求被激发的背景信息？ –

尽管一个反思... - 并不是所有的元素必须是相同的类型才能在所有方向（组合）上互相'isAssignable'？我相信'！CommonType！T == void'不是一个足够的要求。 –

我不认为火卫一有一个，但你可以让你自己有点儿像这样：

void orderInPlace(T...)(ref T t) { 
    import std.algorithm; 
    T[0][T.length] buffer; 
    foreach(idx, a; t) 
     buffer[idx] = a; 
    auto sorted = sort(buffer[]); 
    foreach(idx, a; t) 
     t[idx] = sorted[idx]; 
}

std.algorithm，排序需要一个数组，但这是很容易 - 我们复制的元组成堆栈数组，对它进行排序，然后将信息复制回元组中。所以也许不完美，但它会工作。你可以通过返回t来代替参考。

来源

2014-01-13 23:02:54

我相信我们需要为每个特定的n定义一个过载（或静态ifs），如果我们想要最佳性能，与重复使用'qsort'相比。无论如何。 –

由于这是一个模板，因此每个不同的参数集都会导致一个专门的函数。 –

Aha，所以Phobos'sort'包含了这些专业化。大。 –

这里的排序网络可能是最有效的，因为参数数量较少，并且它们的编号是已知的编译时间（无循环条件）。

气泡分类很适合分类网络化。我把它扔在一起。它的工作原理是很简单的：

import std.stdio, std.string; 

void bubbleSort(T...)(ref T values) 
{ 
    static if (T.length > 1) 
    { 
     foreach(I, _; T[0 .. $ - 1]) 
     { 
      pragma(msg, format("[%s %s]", I, I + 1)); 
      compareAndSwap(values[I], values[I + 1]); 
     } 
     bubbleSort(values[0 .. $ - 1]); 
    } 
} 
void compareAndSwap(T)(ref T a, ref T b) 
{ 
    import std.algorithm; 
    if(a > b) 
     swap(a, b); 
} 

void main() 
{ 
    int a = 10; 
    int b = 30; 
    int c = 11; 
    int d = 20; 
    int e = 4; 
    int f = 330; 
    int g = 21; 
    int h = 110; 
    shellSort(a, b, c, d, e, f, g, h); 
    writefln("%s %s %s %s %s %s %s %s!", a, b, c, d, e, f, g, h); 
}

虽然说实话，如果这是标准库，小于10个参数任何排序网络应该写得一手。

编辑：我彻底改变了以前的算法，这实际上是非常不适应。气泡排序不是最佳，但它实际上排序算法正常。这里有一些编译指令可以查看构建的网络。

来源

2014-01-14 16:08:09

嗯......我做了一些检查，并且这个解决方案实际上产生了非常多的比较器。它*非常低效。 –

元素的就地排序

回答

相关问题