En referencia a fastest sort of fixed length 6 int array, no entiendo completamente cómo este sorting network supera un algoritmo como insertion sort.¿Cómo una red de clasificación vence a los algoritmos de clasificación genéricos?
Formulario esa pregunta, he aquí una comparación del número de ciclos de CPU necesario para completar el tipo:
Linux de 32 bits, GCC 4.4.1, procesador Intel Core 2 Quad Q8300, O2
- ordenación por inserción (Daniel Stutzbach): 1425
- redes de ordenación (Daniel Stutzbach): 1080
El código utilizado es el siguiente:
ordenación por inserción (Daniel Stutzbach)
static inline void sort6_insertion_sort_v2(int *d){
int i, j;
for (i = 1; i < 6; i++) {
int tmp = d[i];
for (j = i; j >= 1 && tmp < d[j-1]; j--)
d[j] = d[j-1];
d[j] = tmp;
}
}
redes de ordenación (Daniel Stutzbach)
static inline void sort6_sorting_network_v1(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(4, 5);
SWAP(3, 5);
SWAP(3, 4);
SWAP(0, 3);
SWAP(1, 4);
SWAP(2, 5);
SWAP(2, 4);
SWAP(1, 3);
SWAP(2, 3);
#undef SWAP
}
I entender d que las redes de clasificación son realmente buenas para ordenar en paralelo, porque algunos de los pasos son independientes de los otros pasos. Pero aquí no estamos usando la paralelización.
Espero que sea más rápido, ya que tiene la ventaja de conocer el número exacto de elementos de antemano. ¿Dónde y por qué exactamente el ordenamiento por inserción hace comparaciones innecesarias?
EDIT1:
Este es el conjunto de entrada de estos códigos se comparan con:
int d[6][6] = {\
{1, 2, 3, 4, 5, 6},\
{6, 5, 4, 3, 2, 1},\
{100, 2, 300, 4, 500, 6},\
{100, 2, 3, 4, 500, 6},\
{1, 200, 3, 4, 5, 600},\
{1, 1, 2, 1, 2, 1}\
};\
¿El orden de la matriz de entrada es aleatorio aquí? ¿O estás usando una matriz descendente? –
@crypto: pregunta actualizada! – Lazer