13

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");
}
2
  • 4
    Note: all complexities are given wrt to some "cost" functions. Quicksort is O(n log n) in average, where n determine the number of comparisons. This has not been chosen arbitrarily, in the case of "regular" computation this is a good indicator of the cost. However when dealing with an unconventional device (here a tape) it would be more accurate to compute the complexity in terms of "moves" of the tape. I think it's a great way to make your students think about what "complexity" is. Commented Feb 7, 2011 at 7:55
  • I have found that actually my algo is a quite much alike the selection sort alogithm in mean of swaps. It is located here: sorting-algorithms.com/selection-sort, if you intererested you can find there a very interesting explanation, where to use a particular alogrithm and their particular pros and cons. Commented Feb 7, 2011 at 10:17

3 Answers 3

32

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(n2), 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(n2) 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(n2) 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.

1
  • +1 I didn't expect to see this full and complete reply so quickly ;) Phanx ;) I will think about it! Commented Feb 7, 2011 at 8:55
11

templatetypedef's answer is right on the money. Not only are bubblesort's accesses minimally spread out, it operates in-place. I suspect it is actually the best sorting algorithm for a machine having a single, arbitrarily slow tape and only O(1) RAM. [EDIT: In fact cocktail sort (a bidirectional version of bubblesort) should be better as it avoids wasteful rewinds -- thanks Steve Jessop.]

If you have 4 tape drives available then mergesort rules the roost. With only 3 tapes, a fancier version of mergesort can be used.

4
  • 1
    I think the conditions for bubble sort to be optimal are even more specific than that, something about 2-head memory drums. Commented Feb 7, 2011 at 13:14
  • @Steve: Sounds interesting, though I don't know what "2-head memory drums" are :) Now I'm wondering what sorting algorithm would be better than bubblesort for the model I described (1 slow tape + O(1) RAM) -- everything I can think of needs either more memory or fast random access. Ideas? Commented Feb 7, 2011 at 13:22
  • 1
    en.wikipedia.org/wiki/Drum_memory, note "a few drum stores such as the Univac FASTRAND had one or more moving heads". With one slow tape IIRC you can do better than bubble sort by doing a similar thing with one bubble pass in one direction, then another bubble pass back again, so as not to have to expensively rewind the tape to get back to the start as you would in a pure bubble sort. Possibly called "cocktail sort"? Commented Feb 7, 2011 at 13:39
  • Thanks @Steve, I was thinking bubblesort was bidirectional but I see now "cocktail sort" is the correct term. Yes it must be better to avoid rewinds. Commented Feb 7, 2011 at 14:17
1

One of the reasons QuickSort is faster than bubble sort is that it instantaneously move elements great distances. If QuickSort moves an element up 50 elements, then down 20, up 10, up 5, and down 2 before it ends up in its proper spot, the element will end up 43 slots from where it started, while having only moved 5 times. Bubble sort would have moved the element 43 times. If moving the element one slot costs the same as moving it by 50, that's a major win. If, however, the cost of moving an element is proportional to the distance, QuickSort will have moved the element a total distance of 87 slots--twice as many as bubble sort.

If one is stuck dealing with tape drives, the optimal algorithm will depend a lot upon how the drives physically work. For example, on some drives the only operations are rewind and prepare for writing (effectively erasing the tape in the process), rewind and prepare for reading, and process the next byte (read or write, depending upon the rewind mode). Other drives allow individual blocks to be randomly accessed and replaced anywhere on the tape. Some drives are limited to reading in one direction. Others (e.g. QIC tapes) have some tracks which read in one direction and some which read in the other direction. I don't know if any drives would allow the same block of data to be read or written in both directions, but such a thing would be at least theoretically possible.

Not the answer you're looking for? Browse other questions tagged or ask your own question.