c - 为什么 C 快速排序函数(磁带比较、磁带交换)比冒泡排序函数慢得多？

Question

我要为学生实现一个玩具磁带“大型机”，展示“quicksort”类函数的快速性(递归与否，并不重要，因为硬件速度慢，以及众所周知的堆栈反转技术) 与“冒泡排序”函数类相比。所以，虽然我很清楚硬件实现和 Controller ，但我猜想快速排序函数在顺序、顺序和比较距离方面比其他函数快得多(从中间倒带比从中间倒带快得多结束，因为倒带速度不同)。

不幸的是，这不是真的；与“快速排序”函数相比，这个简单的“冒泡”代码在比较距离、方向以及比较和写入次数方面有很大改进。

所以我有3个问题:

1. 我在实现快速排序功能时是否有错误？
2. 我在执行 bubblesoft 功能时是否有错误？
3. 如果不是，为什么“冒泡排序”函数(比较和写入操作)比“快速排序”函数快得多？

我已经有了“快速排序”功能:

void quicksort(float *a, long l, long r, const compare_function& compare)
{
    long i=l, j=r, temp, m=(l+r)/2;
    if (l == r) return;
    if (l == r-1)
    {
        if (compare(a, l, r))
        {
            swap(a, l, r);
        }
        return;
    }
    if (l < r-1)
    {
        while (1)
        {
            i = l;
            j = r;
            while (i < m && !compare(a, i, m)) i++;
            while (m < j && !compare(a, m, j)) j--;
            if (i >= j)
            {
                break;
            }
            swap(a, i, j);
        }
        if (l < m) quicksort(a, l, m, compare);
        if (m < r) quicksort(a, m, r, compare);
        return;
    }
}

我有自己的“冒泡排序”函数实现:

void bubblesort(float *a, long l, long r, const compare_function& compare)
{
    long i, j, k;
    if (l == r)
    {
        return;
    }
    if (l == r-1)
    {
        if (compare(a, l, r))
        {
            swap(a, l, r);
        }
        return;
    }
    if (l < r-1)
    {
        while(l < r)
        {
            i = l;
            j = l;
            while (i < r)
            {
                i++;
                if (!compare(a, j, i))
                {
                    continue;
                }
                j = i;
            }
            if (l < j)
            {
                swap(a, l, j);
            }
            l++;
            i = r;
            k = r;
            while(l < i)
            {
                i--;
                if (!compare(a, i, k))
                {
                    continue;
                }
                k = i;
            }
            if (k < r)
            {
                swap(a, k, r);
            }
            r--;
        }
        return;
    }
}

我在测试示例代码中使用了这些排序函数，如下所示:

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

long swap_count;
long compare_count;

typedef long (*compare_function)(float *, long, long );
typedef void (*sort_function)(float *, long , long , const compare_function& );

void init(float *, long );
void print(float *, long );

void sort(float *, long, const sort_function& );
void swap(float *a, long l, long r);

long less(float *a, long l, long r);
long greater(float *a, long l, long r);

void bubblesort(float *, long , long , const compare_function& );
void quicksort(float *, long , long , const compare_function& );

void main()
{
    int n;
    printf("n=");

    scanf("%d",&n);
    printf("\r\n");

    long i;
    float *a = (float *)malloc(n*n*sizeof(float));

    sort(a, n, &bubblesort);
    print(a, n);

    sort(a, n, &quicksort);
    print(a, n);

    free(a);
}

long less(float *a, long l, long r)
{
    compare_count++;
    return *(a+l) < *(a+r) ? 1 : 0;
}

long greater(float *a, long l, long r)
{
    compare_count++;
    return *(a+l) > *(a+r) ? 1 : 0;
}

void swap(float *a, long l, long r)
{
    swap_count++;

    float temp;

    temp = *(a+l);
    *(a+l) = *(a+r);
    *(a+r) = temp;
}

float tg(float x)
{
    return tan(x);
}

float ctg(float x)
{
    return 1.0/tan(x);
}

void init(float *m,long n)
{
    long i,j;
    for (i = 0; i < n; i++)
    {
        for (j=0; j< n; j++)
        {
            m[i + j*n] = tg(0.2*(i+1)) + ctg(0.3*(j+1));
        }
    }
}

void print(float *m, long n)
{
    long i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("  %5.1f", m[i + j*n]);
        }
        printf("\r\n");
    }
    printf("\r\n");
}

void sort(float *a, long n, const sort_function& sort)
{
    long i, sort_compare = 0, sort_swap = 0;

    init(a,n);

    for(i = 0; i < n*n; i+=n)
    {
        if (fmod (i / n, 2) == 0)
        {
            compare_count = 0;

            swap_count = 0;
            sort(a, i, i+n-1, &less);

            if (swap_count == 0)
            {
                compare_count = 0;
                sort(a, i, i+n-1, &greater);
            }

            sort_compare += compare_count;
            sort_swap += swap_count;
        }
    }

    printf("compare=%ld\r\n", sort_compare);
    printf("swap=%ld\r\n", sort_swap);

    printf("\r\n");
}

Answer 1

我认为问题在于大多数快速排序实现依赖于分区步骤，该步骤在要排序的区域的两端交替读取和写入。在随机访问模型中，这非常好(所有读取基本上都是 O(1))，但在磁带上，这可能非常昂贵，因为在要排序的范围的不同端点之间来回交换可能需要 O( n) 磁带卷轴前后滚动的时间。这将通常是 O(n) 的分区步骤变成了潜在的 O(n²)，从而控制了函数的运行时间。此外，由于进行磁带寻道所需的时间可能比处理器的频率慢数千或数百万倍，因此此 O(n²) 工作具有巨大的常数因子。

另一方面，冒泡排序没有这个问题，因为它总是比较数组中的相邻单元格。它最多使 O(n) 遍历数组，因此只需要将磁带倒带 n 次。处理逻辑在冒泡排序中肯定更昂贵 - 比几乎任何其他 O(n²) 排序都要多 - 但与不来回查找磁带所节省的时间相比，这算不了什么。

简而言之，快速排序在磁带上的运行速度可能比冒泡排序慢得多，因为它需要磁带在执行过程中移动得更多。由于 tape seeking 的成本很高，因此 quicksort 的天然运行时优势将在此步骤中被吃掉，而 bubblessort 看起来应该快得多。