非遞歸的快速排序在RCPP

Question

我Rcpp使用recursive quick排序算法與此代碼：

void Quick(NumericVector arr,int left,int right) { 
    int i=left;int j=right; 
    double tmp; 
    double pivot=arr[(left+right)/2]; 
    while(i<=j){ 
    while(arr[i]<pivot) 
     i++; 
    while(arr[j]>pivot) 
     j--; 
     if(i<=j){ 
     tmp=arr[i]; 
     arr[i]=arr[j]; 
     arr[j]=tmp; 
     i++; 
     j--; 

     } 
    } 
    if(left<j) 
    Quick(arr,left,j); 
    if(i<right) 
    Quick(arr,i,right); 
} 


    // [[Rcpp::export]] 
    NumericVector sort_quick(NumericVector A) { 
     NumericVector tmp=clone(A); 
     Quick(tmp,0,tmp.size()-1); 
     return tmp; 
    } 

我怎樣才能得到一個iterative進程加快的代碼？

Answer 1

在快速排序的常見迭代實現中，您使用本地數組模擬調用堆棧。完成對子數組的分區時，您會檢查分區索引左側是否有元素。如果是這樣，你將一對索引推到代表該子陣列的「堆棧」上。然後，對分區索引右側的子數組執行相同操作。在循環的下一次迭代中，您從堆棧中彈出一對子數組索引，在該子數組上執行分區，然後執行上面所述的操作。

http://www.geeksforgeeks.org/iterative-quick-sort/

我不知道的是，性能增益是這是超級顯著，但它可能是什麼。

對於非常大的輸入大小，您可能會考慮做的另一件事是從矢量中提取元素並將它們放入緩衝區，然後對緩衝區進行排序。至少對於一個std :: vector來說，訪問開銷似乎大約是直接進入內存的兩倍，所以一旦你通過了一定的輸入大小閾值，這就變得值得。這是我在實現並行mergesort算法時偶然發現的。