Voy a implementar una cinta de juguete "mainframe" para los estudiantes, mostrando la rapidez de las funciones de clase "quicksort" (recursivas o no, en realidad no importa, debido al hardware lento y las conocidas técnicas de inversión de pila) en comparación con la clase de función "bubblesort". Entonces, aunque tengo clara la implementación del hardware y los controladores, supuse que la función de conexión rápida es mucho más rápida que otras en términos de secuencia, orden y distancia de comparación (es mucho más rápido rebobinar la cinta desde el medio que desde el mismo fin, debido a la diferente velocidad de rebobinado).¿Por qué la función de envío rápido de C es mucho más lenta (comparaciones de cinta, intercambio de cintas) que la función de ordenación de burbujas?
Lamentablemente, esto no es cierto; Este simple código de "burbuja" muestra grandes mejoras en comparación con las funciones de "quicksort" en términos de distancias de comparación, dirección y número de comparaciones y escrituras.
así que tengo 3 preguntas:
- ¿Tiene Tengo un error en mi implememtation de la función de la clasificación rápida?
- ¿Tengo un error en la implementación de la función bubblesoft?
- Si no es así, ¿por qué la función "bubblesort" es mucho más rápida en operaciones de comparación y escritura que en la función "quicksort"?
ya tengo una función de "ordenación rápida":
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;
}
}
y tengo mi propia implementación de la función "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;
}
}
he utilizado estas funciones de clasificación en una Código de ejemplo de prueba, como este:
#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");
}
Nota: todas las complejidades se otorgan a algunas funciones de "costo". Quicksort es O (n log n) en promedio, donde 'n' determina el número de comparaciones. Esto no se ha elegido arbitrariamente, en el caso del cálculo "regular" este es un buen indicador del costo. Sin embargo, cuando se trata de un dispositivo no convencional (aquí una cinta), sería más preciso calcular la complejidad en términos de "movimientos" de la cinta. Creo que es una excelente manera de hacer que sus alumnos piensen en lo que es "complejidad". –
He encontrado que en realidad mi algo es bastante parecido al algoritmo de ordenación de selección en la media de los intercambios. Se encuentra aquí: http://www.sorting-algorithms.com/selection-sort, si está interesado puede encontrar allí una explicación muy interesante, dónde usar un alogrithm particular y sus ventajas y desventajas particulares. –