C randomized pivot quicksort(改进分区函数)

Question

我是一名计算机科学专业的学生(刚开始)，我正致力于用伪代码编写一个随机主元版本的快速排序。我已经编写并测试了它，但是它一切正常......

分区部分看起来有点复杂，感觉漏掉了一些东西或者想多了。我不明白是否可以，或者我是否犯了一些可以避免的错误。

长话短说:它有效，但如何做得更好？

提前感谢所有的帮助

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's Partitioning Algorithm，伪代码如下:

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

划分后，A[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)