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:
- Does I have a mistake in my implememtation of quicksort function?
- Does I have a mistake in my implememtation of bubblesoft function?
- 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");
}
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.