Estoy buscando un algoritmo de ordenación para matrices int que no asigne ningún byte que no sea el tamaño de la matriz, y se limita a dos instrucciones:
SWAP: intercambia el siguiente índice con el actual;
MOVER: mueve el cursor al índice +1 o -1;
Es decir, no puede intercambiar índices no vecinos, ni intercambiar el índice 100
, después de haber intercambiado el índice 10
. ¿Cuál es el algoritmo más eficiente, es decir, el que usa la menor cantidad de movimientos totales?
algorithms
sorting
in-place
MaiaVictor
fuente
fuente
Respuestas:
Considere el tipo de coctelera , que es una versión bidireccional del tipo burbuja. Usted burbujea de bajo a alto, y luego (esta es la parte añadida) burbujea de alto a bajo, repita hasta que esté listo. Esto sigue siendo , pero hace significativamente menos pases en promedio, porque los elementos pequeños cerca del extremo superior de la matriz se moverán a su posición final en un solo pase en lugar de N pases. Además, puede realizar un seguimiento de las posiciones más bajas y más altas donde se produjo un intercambio; los pases posteriores no necesitan escanear más allá de esos puntos.O ( n2)
fuente
El número de intercambios de elementos adyacentes necesarios para ordenar una matriz es igual a la cantidad de inversiones en la matriz. Con n elementos en total, hay a lo sumo n * (n-1) / 2 inversiones, por lo que la ordenación de burbujas da el número asintóticamente óptimo de intercambios en este modelo.
fuente
El único algoritmo con los dos operadores que ha mencionado que es bastante eficiente es el tipo de burbuja. La complejidad del algoritmo esO ( n2)
El algoritmo que no usa una bandera booleana para saber si hemos intercambiado algún elemento o no, se da a continuación (el truco para mantener la información en el estado de la máquina, en lugar de la memoria):
La solución de Eric Lippert, el gnomo también funciona, porque básicamente es un tipo de burbuja de dos vías.
fuente