Ideológico:
- Elige cualquier elemento.
- Separe todos los elementos para los más pequeños y más grandes.
- Ahora puede simplemente ordenar cada una de estas dos partes por separado.
Implementacional:
- Elija un elemento al azar de todos los elementos (si elige el elemento al azar, entonces, para cada secuencia para ordenar, tiene una probabilidad mínima de que su algoritmo funcione más lento de lo esperado. Si elige cualquier elemento pero no al azar [por ejemplo, simplemente toma el primero] entonces existe una probabilidad mínima de que su algoritmo funcione más lento de lo esperado, pero siempre sucederá en la misma secuencia de entrada y si resulta que esta secuencia es popular por alguna razón, su algoritmo funciona muy mal. prefiero lo primero)
- Separe todos los elementos para los más pequeños y más grandes.
- Esto se puede hacer de varias maneras. Lo más trivial pero no tan malo es simplemente crear matrices adicionales a las que asignará todos los elementos más pequeños / más grandes que el elegido, y solo al final los reescribirá en la matriz original. Debe tener cuidado con los elementos iguales al elegido porque decidir que una parte será “más pequeña” y la otra “más grande o igual” daría resultados catastróficos, por ejemplo, en una secuencia como 1 1 1 1 1 1 1. Probablemente sea mejor para tratar elementos iguales como otra tercera categoría.
- Para evitar estos inconvenientes, hay otras formas de hacer la partición, por ejemplo, la más popular de Hoare:
p = 0, q = fin
repetir
mientras que la entrada [p] <elegido_elemento // no debería ser <=!
p ++
mientras que entrada [q]> elemento_elegido
q–
si (p> = q)
regreso
- ¿Vale la pena pagar 6 x $ 49 por una estructura de datos y especialización de algoritmos en Coursera?
- Si arr es una matriz de enteros, ¿por qué la expresión ar ++ no es legal?
- ¿Cómo visualizo el laberinto que estoy creando?
- ¿Qué enfoque debe adoptar en la vida, un paradigma codicioso o un enfoque de programación dinámica?
- ¿Cómo podemos verificar de forma recursiva si una lista vinculada individualmente es un palíndromo?
// ahora tenemos una situación en la que todo antes del índice p
// es un fragmento correcto de elementos <= elegido
// todo después de q es el fragmento correcto de> = elegido
swap (entrada [p], entrada [q])
p ++, q–
- Esta versión tarda un momento en comprender por qué funciona (especialmente por qué resuelve problemas de tipo “1 1 1 1 1 ″). Por ejemplo, puede dibujar algún ejemplo con varios valores repetidos y ver cómo lo divide, pero es bastante efectivo y breve. codificar.
- Llame a la función de forma recursiva en los fragmentos creados.
