Why does C qicksort function implementation works much slower (tape comparations, tape swapping) than bobble sort function?
- by Artur Mustafin
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 matters, due to the slow hardware, and well known stack reversal techniques) comparatively to the "bubblesort" function class, so, while I'm clear about the hardware implementation ans controllers, i guessed that quicksort function is much faster that other ones in terms of sequence, order and comparation 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 the true, this simple "bubble" code shows great improvements comparatively to the "quicksort" functions in terms of comparison distances, direction and number of comparisons and writes.
So I have 3 questions:
Does I have mistaken in my implememtation of quicksort function?
Does I have mistaken in my implememtation of bubblesoft function?
If not, why the "bubblesort" function is works 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 the kind of my own implememtation 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 this 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");
}
