Why is C quicksort function much slower (tape comparisons, tape swapping) than bubble sort function?

Question

I'm going to implement a toy tape "mainframe" for a students, showing the quickness of "quicksort" class functions (recursive or not, does not really matter, due to the slow hardware, and well known stack reversal techniques) compared to the "bubblesort" function class. So, while I'm clear about the hardware implementation and controllers, I guessed that quicksort function is much faster than other ones in terms of sequence, order and comparison distance (it is much faster to rewind the tape from the middle than from the very end, because of different speed of rewind).

Unfortunately, this is not true; this simple "bubble" code shows great improvements compared to the "quicksort" functions in terms of comparison distances, direction and number of comparisons and writes.

So I have 3 questions:

1. Does I have a mistake in my implememtation of quicksort function?
2. Does I have a mistake in my implememtation of bubblesoft function?
3. If not, why is the "bubblesort" function so much faster in (comparison and write operations) than "quicksort" function?

I already have a "quicksort" function:

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

and I have my own implementation of the "bubblesort" function:

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

I have used these sort functions in a test sample code, like this:

#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.