快速排序"lomuto"分区算法：交替实现分析

Question

请考虑经典算法教科书中的快速排序“lomuto 分区”方案算法导论作者Cormen、Leiserson、Rivest & Stein.

PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

实现这个算法后，我发现它并不能正常工作，最多也就是差1个元素。然后我开始计算解决方案并最终得出以下有效的 C 代码。我已经在代码中评论了算法的工作原理。

int quickSortPartition(int *array, int beginIndex, int endIndex) // end index = array length - 1.
{
    int pivotIndex = beginIndex; // first element as pivot.
    int pivotValue = array[pivotIndex]; // initial pivot value.
    int i = beginIndex + 1; // start loop with i being 2nd index.
    while(i < endIndex) // loop running until end of array.
    {
        if(array[i] > array[i + 1]) // comparing the 2 elements ahead of pivot.
        {
            swap(array, i, i + 1); // swapping the 2 elements if prev element > next element.
        }
        if(array[i] < pivotValue) // comparing element at pivot index with the next index element.
        {
            swap(array, pivotIndex, i); // swapping if next element is less than element at pivot index.
            ++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
        }
        ++i; // drive loop.
    }
    if(array[pivotIndex] > array[pivotIndex + 1]) // at the very end, compare whether the element to the right of pivot is > element at pivot index.
    {
        swap(array, pivotIndex, pivotIndex + 1); // swapping if next element is less than element at pivot index.
        ++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
    }
    return pivotIndex; // returning new pivot index.
}

我的实现效率是否低于书中所谓的“lomuto 分区”？当然，它们都是 O(n)，但是就一次迭代中的赋值和比较等原子操作而言呢？它对大规模案例的效率有显着影响吗？为什么书上的算法不行？它缺少什么部分？我也很感激有关如何进一步简化我的代码的建议。

其他后续信息：

我已经在 python 中实现了本书的代码。

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r - 1):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

array = [2, 55, 43, 12, 65, 72, 41, 18, 6]
print(array)
quicksort(array, 0, len(array) - 1)
print(array)

结果：

unsorted: [2, 55, 43, 12, 65, 72, 41, 18, 6]
sorted: [2, 6, 41, 43, 12, 55, 65, 72, 18]

如您所见，排序失败。另外，如果我将 len(array) 用作第三个参数，则会出现溢出错误。

至于我的 C 代码，使用我的算法并工作，这是我的头文件，您可以测试。

#ifndef A1_H
#define A1_H

// am1n

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

void printArray(int *array, int arrayLength)
{
    int i = 0;
    --arrayLength;
    for(i = 0; i < arrayLength; ++i)
    {
        printf("%d, ", array[i]);
    }
    printf("%d.\n", array[i]);
}

void swap(int *array, int a, int b)
{
    if(array[a] != array[b])
    {
        int tempValue = array[a];
        array[a] = array[b];
        array[b] = tempValue;
    }
}

int fastSortPartition(int *array, int beginIndex, int endIndex) // end index = array length - 1.
{
    int pivotIndex = beginIndex; // first element as pivot.
    int pivotValue = array[pivotIndex]; // initial pivot value.
    int i = beginIndex + 1; // start loop with i being 2nd index.
    while(i < endIndex) // loop running until end of array.
    {
        if(array[i] > array[i + 1]) // comparing the 2 elements ahead of pivot.
        {
            swap(array, i, i + 1); // swapping the 2 elements if prev element > next element.
        }
        if(array[i] < pivotValue) // comparing element at pivot index with the next index element.
        {
            swap(array, pivotIndex, i); // swapping if next element is less than element at pivot index.
            ++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
        }
        ++i; // drive loop.
    }
    if(array[pivotIndex] > array[pivotIndex + 1]) // at the very end, compare whether the element to the right of pivot is > element at pivot index.
    {
        swap(array, pivotIndex, pivotIndex + 1); // swapping if next element is less than element at pivot index.
        ++pivotIndex; // incrementing pivot index by 1 ONLY when swap occurs.
    }
    return pivotIndex; // returning new pivot index.
}

void fastSort(int *array, int beginIndex, int endIndex)
{
    if(beginIndex < endIndex)
    {
        int pivotIndex = fastSortPartition(array, beginIndex, endIndex);
        fastSort(array, beginIndex, pivotIndex - 1);
        fastSort(array, pivotIndex + 1, endIndex);
    }
}

#endif

Answer 1

将循环上限修改为合适的值即可解决

for j in range(p, r):

注意Python范围不包括右边界，pivot保持在末尾直到分区结束

您的示例的结果

[2, 6, 12, 18, 41, 43, 55, 65, 72]

Answer 2

令 N 为正在处理的子数组中的元素数。
令 L 为最终落入数组左侧部分的项目数 - 小于或等于原始算法中的主元，小于代码中的主元加上主元本身。

这两个例程都必须对数组进行 N-1 步和 N-1 次比较，以检查每个元素并识别那些小于或小于或等于主元的元素。原始例程进行的比较次数恰好相同。但是你的代码做了两倍的事情：在循环的每次迭代中，它比较 array[i] 到 pivotValue AND array[i] 到 array[i + 1].

这两个例程还必须几乎恰好进行 L 次交换以将这些较小的项目组合在一起，再加上最多两次交换以暂时将枢轴移开并放回原位。但是您的代码可能会进行 N–1 次额外交换，以将 'big' 元素向右推，但没有显着增益。

所以答案是：不，你提出的代码肯定没有比原始算法更有效，无论是在多次比较还是多次交换中。

您的代码所做的工作（基本操作）大约是 Lomuto 方法的两倍。但这只是一个比例因子；渐进地考虑它们都是线性的，O(N)。

事实证明我是对的：您的实现不是 Lomuto 算法 – 由于 for j in range() 的不正确使用，您没有按照原始例程的要求测试数组的最后一项。

快速排序"lomuto"分区算法：交替实现分析

Quick sort "lomuto" partition algorithm: alternate implementation analysis

c

sorting

algorithm

quicksort