C隨機樞軸快速排序（改進分區功能）

Question

我是一名計算機科學專業的學生（剛開始），我正在從僞代碼編寫Quicksort的隨機化樞軸版本。我已經編寫並測試了它，但它仍然完美地工作，但是...

分區部分看起來有點太複雜，因爲它感覺我錯過了某些東西或者推翻了它。我無法理解，如果沒關係，或者我犯了一些可以避免的錯誤。

這麼久以來的故事很短：它有效，但如何做得更好？

預先感謝所有幫助

void partition(int a[],int start,int end) 
{ 
    srand (time(NULL)); 
    int pivotpos = 3; //start + rand() % (end-start); 
    int i = start; // index 1 
    int j = end;  // index 2 
    int flag = 1; 
    int pivot = a[pivotpos]; // sets the pivot's value 
    while(i<j && flag)  // main loop 
    { 
     flag = 0; 
     while (a[i]<pivot) 
     { 
      i++; 
     } 
     while (a[j]>pivot) 
     { 
      j--; 
     } 
     if(a[i]>a[j]) // swap && sets new pivot, and restores the flag 
     { 
      swap(&a[i],&a[j]); 
      if(pivotpos == i) 
       pivotpos = j; 
      else if(pivotpos == j) 
       pivotpos = i; 
      flag++; 
     } 
     else if(a[i] == a[j])  // avoids getting suck on a mirror of values (fx pivot on pos 3 of : 1-0-0-1-1) 
     { 
      if(pivotpos == i) 
       j--; 
      else if(pivotpos == j) 
       i++; 
      else 
      { 
       i++; 
       j--; 
      } 
      flag++; 
     } 
    } 
} 

Answer 1

這是Introduction to Algorithms的partition()的僞代碼，這就是所謂Lomuto的劃分算法，並有在書下面有個很好的解釋。

PARTITION(A, p, r) 
1 x ← A[r] 
2 i ← p - 1 
3 for j ← p to r - 1 
4 do if A[j] ≤ x 
5  then i ←i + 1 
6   exchange A[i] ↔ A[j] 
7 exchange A[i + 1] ↔ A[r] 
8 return i +1 

您可以根據上面的僞代碼輕鬆實現隨機分區實現。正如評論指出的那樣，將srand()移出partition。

// srand(time(NULL)); 
int partition(int* arr, int start, int end) 
{ 
    int pivot_index = start + rand() % (end - start + 1); 
    int pivot = arr[pivot_index ]; 

    swap(&arr[pivot_index ], &arr[end]); // swap random pivot to end. 
    pivot_index = end; 
    int i = start -1; 

    for(int j = start; j <= end - 1; j++) 
    { 
     if(arr[j] <= pivot) 
     { 
      i++; 
      swap(&arr[i], &arr[j]); 
     } 
    } 
    swap(&arr[i + 1], &arr[pivot_index]); // place the pivot to right place 

    return i + 1; 
} 

並且有書中，這被稱爲霍爾的劃分算法中提到的另一個分區的方法，所述僞碼如下：

Hoare-Partition(A, p, r) 
x = A[p] 
i = p - 1 
j = r + 1 
while true 
    repeat 
     j = j - 1 
    until A[j] <= x 
    repeat 
     i = i + 1 
    until A[i] >= x 
    if i < j 
     swap(A[i], A[j]) 
    else 
     return j 

分區後，所述的[P的每一個元素。 ..j]≤A[j + 1 ... r]中的每個元素。所以快速排序是：

QUICKSORT (A, p, r) 
if p < r then 
q = Hoare-Partition(A, p, r) 
QUICKSORT(A, p, q) 
QUICKSORT(A, q+1, r) 

Answer 2

快速排序有多種分區方式，以下可能是最簡單的我可以召集。一般分區的兩個流派被使用：

1. 的擠壓 - 摺疊該序列的兩端，直至一個適當的交換對被發現，然後交換兩個元素向分區的適當側面。不平凡的實現，但可以更高效（減少交換次數）比其他...
2. 掃頻 - 使用單一從左到右（或從右到左）掃值，交換值隨着算法運行而增加的樞軸索引。很容易實現，如下所示。

對於學習快速排序和分區的人來說，我更喜歡Sweep算法，因爲它實在太簡單了。兩者都可以被執行來執行就地分區，就像在下面的實現中那樣。除了在swap()以外，您不會看到存儲在臨時存儲器中的值。

使用隨機數據透視選擇只是其中的一小部分。下面顯示瞭如何初始化隨機數生成器，並演示其中最簡單的分區算法和快速排序。

它演示了，除此之外，在C/C++中，由於可以使用簡單指針算術來調整分區的「頂部」一半，因此不需要分區的兩端。請參閱quicksort()函數了解如何完成此操作。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

void swap(int *lhs, int *rhs) 
{ 
    if (lhs == rhs) 
     return; 

    int tmp = *lhs; 
    *lhs = *rhs; 
    *rhs = tmp; 
} 

int partition(int ar[], int len) 
{ 
    int i, pvt=0; 

    // swap random slot selection to end. 
    // ar[len-1] will hold the pivot value. 
    swap(ar + (rand() % len), ar+(len-1)); 
    for (i=0; i<len; ++i) 
    { 
     if (ar[i] < ar[len-1]) 
      swap(ar + i, ar + pvt++); 
    } 

    // swap the pivot value into position 
    swap(ar+pvt, ar+(len-1)); 
    return pvt; 
} 

void quicksort(int ar[], int len) 
{ 
    if (len < 2) 
     return; 

    int pvt = partition(ar, len); 
    quicksort(ar, pvt++); // note increment. skips pivot slot 
    quicksort(ar+pvt, len-pvt); 
} 


int main() 
{ 
    srand((unsigned int)time(NULL)); 

    const int N = 20; 
    int data[N]; 

    for (int i=0; i<N; ++i) 
    { 
     data[i] = rand() % 50 + 1; 
     printf("%d ", data[i]); 
    } 
    puts(""); 

    quicksort(data, N); 

    for (int i=0; i<N; ++i) 
     printf("%d ", data[i]); 

    puts(""); 

    return 0; 
} 

輸出（不同，很明顯）

32 49 42 49 5 18 41 48 22 33 40 27 12 47 41 6 50 27 8 7 
5 6 7 8 12 18 22 27 27 32 33 40 41 41 42 47 48 49 49 50 

注：這不佔模偏置使用rand() % len，並坦言這將是矯枉過正在這個例子中這樣做。如果它很重要，我會完全使用另一臺發電機。一個優秀的討論的方法選擇隨機樞紐位置快速分區can be found at this post on this site，包括許多鏈接到不同的方法。我建議審查它。