Una forma de medir qué tan desordenada es una secuencia [matemática] a_1, \ ldots, a_n [/ matemática] es contar el número de pares [matemática] a_i <a_j, j <i [/ matemática]. Esto es básicamente un recuento de pares que están fuera de servicio. Para una secuencia completamente ordenada, este recuento es 0, para una secuencia en orden inverso, se trata de [matemáticas] \ frac {n ^ 2-n} {2} [/ matemáticas].
Veamos qué sucede cuando intercambiamos un par fuera de secuencia:
Si el par son dos elementos adyacentes, cámbielos reduciendo el recuento de pares fuera de orden en 1.
- ¿Cuál es el algoritmo más genial (programación competitiva) que hayas encontrado?
- ¿Se puede utilizar el aprendizaje automático para encontrar públicos objetivo para anuncios?
- ¿Por qué conocer estructuras de datos y algoritmos básicos no es suficiente para descifrar la mayoría de las entrevistas técnicas?
- ¿Los algoritmos están optimizados para discos duros normales * no * optimizados para unidades de estado sólido?
- ¿Cómo se implementan las matrices de JavaScript internamente?
Si el par no es adyacente, entonces tiene [math] (\ ldots, a_i, \ ldots, a_k, \ ldots, a_j), a_j <a_i [/ math], hay tres casos:
- [matemáticas] a_k <a_j <a_i [/ matemáticas]. En este caso, [math] a_k [/ math] comienza en orden en relación con [math] a_j [/ math] y fuera de orden en relación con [math] a_i [/ math]. Intercambiar los dos hace que [math] a_k [/ math] esté fuera de orden en relación con [math] a_j [/ math], y en orden en relación con [math] a_i [/ math]. El resultado neto es que [math] a_k [/ math] no cambia el conteo fuera de orden cuando se intercambian [math] a_i, a_j [/ math].
- [matemáticas] a_j <a_i <a_k [/ matemáticas]. Como en el último caso, [math] a_k [/ math] está en orden en relación con uno de los pares, pero no en el otro, y cambiarlos cambia a cuál está en orden en relación.
- [matemáticas] a_j <a_k <a_i [/ matemáticas]. En este caso, antes del intercambio, [math] a_k [/ math] está fuera de orden con ambos lados del par, y después del intercambio [math] a_k [/ math] está en orden con ambos. El recuento fuera de servicio se reduce en dos.
Entonces, al intercambiar un par fuera de orden, reduce el recuento fuera de orden en 1, más el número de elementos en la secuencia entre los dos que están numéricamente entre los valores del par fuera de orden. Nunca puede aumentar el número de pares fuera de orden intercambiando un par arbitrario fuera de orden. Si sigue intercambiando pares arbitrarios fuera de orden, eventualmente conducirá el número de pares fuera de orden a cero, y así obtendrá una lista ordenada.
Puede crear una serie de algoritmos de clasificación basados en el intercambio de pares adyacentes, pero cada intercambio solo reducirá el número fuera de orden en 1, lo que significa que podría tomar alrededor de [math] n ^ 2 [/ math] swaps en orden para ordenar la secuencia Esto puede ser ineficiente. El “Tipo de burbuja”, que funciona de esa manera, generalmente se considera el epítome de un tipo ineficiente. No aprovecha las grandes caídas en el recuento fuera de orden que obtiene de una gran cantidad de elementos entre los elementos intercambiados.
Puede desarrollar una clasificación intercambiando elementos totalmente aleatorios fuera de orden, pero el aspecto “totalmente aleatorio” ralentiza bastante las cosas. Puede elegir dos elementos aleatorios [matemática] 1 \ leq i <j \ leq n [/ matemática] con bastante facilidad, verifique si están fuera de orden, luego cámbielos. El problema proviene del hecho de que tiene [matemática] \ frac {n ^ 2-n} {2} [/ matemática] posibles pares de elementos, por lo que está eligiendo aleatoriamente uno de esos. Si tiene, digamos, un millón de elementos, eso significa que tiene alrededor de 500 mil millones de pares posibles. Si la secuencia está casi ordenada, por lo que solo hay 500 pares fuera de orden, entonces tendrá que verificar aleatoriamente alrededor de mil millones de pares aleatorios solo para encontrar 1 de esos, luego otros mil millones de pares para encontrar otro, etc. Y la aleatoriedad significa que nunca se garantiza que encuentres ningún par. Esto es peor que la clasificación de burbujas, que siempre se garantiza que terminará.
Otros algoritmos de clasificación en el lugar funcionan mediante diferentes estrategias para encontrar pares fuera de lugar para intercambiar.
Los tipos de inserción dividen la secuencia en una porción “ordenada” y una porción “no ordenada”, y usan el equivalente de intercambios en el lugar para mover cada elemento desde el lado “no ordenado” a su lugar apropiado en la porción “ordenada”.
Los tipos de selección también dividen la secuencia en una porción “ordenada” y una porción “no ordenada”, pero busca en la porción no ordenada el elemento más pequeño, luego intercambia con el primer elemento en la porción no ordenada.
Quick-sorts selecciona un “valor de pivote” que se considera (con suerte) en el medio del rango de los elementos, luego usa swaps para dividir la secuencia en dos partes, una parte baja (menor que el valor de pivote) y una parte alta (mayor que el valor de pivote). Luego ordena recursivamente las dos partes. Cuando está hecho, entonces todo está ordenado.
Los tipos de pila comienzan comparando todos los triples [matemática] a_i, a_ {2i}, a_ {2i + 1}, 2i \ leq n [/ matemática], e intercambiando un par para que [matemática] a_i [/ matemática] sea el más grande del triple, comenzando desde [matemática] i = n / 2 [/ matemática] hasta [matemática] i = 1 [/ matemática]. Esto crea un “montón”, donde para todas [matemáticas] i [/ matemáticas], los elementos [matemáticas] a_i> a_ {2i}, a_ {2i + 1} [/ matemáticas]. Una vez hecho esto, tiene [math] a_1 [/ math] es el elemento más grande, y puede intercambiarlo con [math] a_n [/ math], y “arreglar” el montón utilizando un número relativamente pequeño de intercambios. Una vez que se arregla el montón, vuelva a intercambiar la parte superior e inferior del montón, reduzca el montón en un elemento y vuelva a arreglarlo. Esto es casi tan rápido como una clasificación rápida.
Una parte relativamente pequeña (pero importante) de la informática es comprender las compensaciones de estos (y otros) algoritmos diferentes.
