为什么C快速排序功能比气泡排序功能慢得多(磁带比较,磁带交换)？

Question

我将为学生实现一个玩具磁带"大型机",显示"快速排序"类功能的快速性(递归与否,由于硬件速度慢,并且众所周知的堆栈反转技术并不重要) "bubblesort"函数类.因此,虽然我清楚硬件实现和控制器,但我猜测,快速排序功能在顺序,顺序和比较距离方面要比其他功能快得多(从中间回放磁带要快得多)结束,因为倒带速度不同).

不幸的是,事实并非如此; 这个简单的"气泡"代码在比较距离,方向和比较和写入次数方面与"快速排序"功能相比显示出很大的改进.

所以我有3个问题:

1. 我实施快速排序功能时是否有错？
2. 我在实现bubblesoft功能时遇到了错误吗？
3. 如果没有,为什么"bubblesort"在(比较和写入操作)中的功能比"quicksort"功能快得多？

我已经有了"quicksort"功能:

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;
    }
}

我有自己的"bubblesort"功能的实现:

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

I think that the problem is that most quicksort implementations rely on a partition step that alternates reads and writes on opposite ends of the region to be sorted. In a random-access model this is perfectly fine (all reads are essentially O(1)), but on a tape this can be extremely expensive, since swapping back and forth between the different ends of the range to be sorted can take O(n) time as the tape reel rolls all the way forwards and backwards. This turns what normally is an O(n) partitioning step into something that's potentially O(n²), dominating the runtime of the function. Moreover, since the time required to do a tape seek is probably thousands or millions of times slower than the processor's frequency, this O(n²) work has a huge constant factor.

Bubble sort, on the other hand, doesn't have this problem because it always compares adjacent cells in the array. It makes at most O(n) passes over the array, and thus requires the tape to be rewound only n times. The processing logic is definitely more expensive in bubble sort - more so than almost any other O(n²) sort - but this is nothing compared to the time saved not seeking the tape back and forth.

In short, quicksort should probably run much slower on a tape than bubble sort simply because it requires the tape to move a lot more during execution. Since tape seeking is expensive, the natural runtime advantage of quicksort will get eaten up in this step, and bubblesort should look much faster.

Answer 2

templatetypedef的答案是正确的钱.bubbleort的访问不仅极少分散,而且可以就地运行.我怀疑它实际上是具有单个,任意慢速磁带和仅O(1)RAM的机器的最佳排序算法. [编辑:实际上鸡尾酒排序(bubbleort的双向版本)应该更好,因为它避免了浪费的倒带 - 感谢Steve Jessop.]

如果你有4个磁带驱动器可用,那么归并排序规则中称雄.只有3个磁带,可以使用更高版本的mergesort.