元素的就地排序

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

嗯......我做了一些檢查，並且這個解決方案實際上產生了非常多的比較器。它*非常低效。 –

元素的就地排序

回答

相關問題