Я собираюсь реализовать игрушечную ленту "мэйнфрейм" для студентов, показывающую быстроту функций класса "быстрой сортировки" (рекурсивных или нет, на самом деле не имеет значения, из-за медленного аппаратного обеспечения и хорошо известных методов обращения стека) ) по сравнению с классом функций "bubblesort". Так что, хотя я и разбираюсь в аппаратной реализации и контроллерах, я догадался, что функция быстрой сортировки намного быстрее, чем другие, с точки зрения последовательности, порядка и расстояния сравнения (гораздо быстрее перематывать ленту с середины, чем с самой конец, из-за разной скорости перемотки).
К сожалению, это не так; этот простой «пузырьковый» код демонстрирует значительные улучшения по сравнению с функциями «быстрой сортировки» с точки зрения расстояний сравнения, направления и количества сравнений и записей.
Итак, у меня есть 3 вопроса:
- Есть ли у меня ошибка в реализации функции быстрой сортировки?
- Есть ли у меня ошибка в моей реализации функции bubblesoft?
- Если нет, то почему функция «пузырьковая сортировка» намного быстрее (операции сравнения и записи), чем функция «быстрой сортировки»?
У меня уже есть функция быстрой сортировки:
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");
}