Que es el ordenamiento rápido quicksort
El ordenamiento
rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y
vencerás, que permite, en promedio, ordenar n elementos en un tiempo
proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida.
Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es
recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento
(los algoritmos recursivos son en general más lentos que los iterativos, y
consumen más recursos).
El algoritmo
fundamental es el siguiente:
·
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos
pivote.
·
Resituar los demás elementos de la lista a cada lado del pivote, de
manera que a un lado queden todos los menores que él, y al otro los mayores. En
este momento, el pivote ocupa exactamente el lugar que le corresponderá en la
lista ordenada.
·
La lista queda separada en dos sublistas, una formada por los elementos
a la izquierda del pivote, y otra por los elementos a su derecha.
·
Repetir este proceso de forma recursiva para cada sublista mientras
éstas contengan más de un elemento. Una vez terminado este proceso todos los
elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo
depende de la posición en la que termine el pivote elegido.
· En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
· En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.
· En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría
de optimizaciones que se aplican al algoritmo se centren en la elección del
pivote.
1. En esta primera parte
iniciamos declarando e inicializando un vector de veinte posiciones de forma
aleatoria
2. luego creamos e inicializamos un objeto mediante el cual pasaremos el vector con todos los parámetros para a otro método de otra clase llamado quicksort2 en el cual ordenaremos el vector aplicando el método quicksort.
3. luego mandamos a recorrer el vector para mostrarlo de forma ordenada
2. luego creamos e inicializamos un objeto mediante el cual pasaremos el vector con todos los parámetros para a otro método de otra clase llamado quicksort2 en el cual ordenaremos el vector aplicando el método quicksort.
3. luego mandamos a recorrer el vector para mostrarlo de forma ordenada
4. En
esta parte mandamos un vector por parámetro con todas las posiciones del vector
junto con los extremos derecho e izquierdo del vector
5. luego condicionamos que si lado izquierdo es mayor o igual al lado derecho entonces se debe retornar el vector
6. asignamos a i lo que tenga lado izquierdo y a d lo que tenga lado derecho
7. luego condicionamos que si lado izquierdo diferente de lado derecho entonces se crean pivote y auxiliar no obstante pivote se le asigna el lado izquierdo
8. luego asignamos el siclo while que pregunta si lado izquierdo diferente de lado derecho entonces se hace lo siguiente
9. otro siclo while que dice que el vector con la posición de lado derecho debe ser mayor e igual al vector en la posición de pivote y también que lado izquierdo debe ser menor que lado derecho, si esto se cumple entonces lado derecho disminuye una posición
10. en el siguiente while dice que si el vector en la posición izquierda es menor que el vector en la posición pivote y lado izquierdo menor que lado derecho entonces lado izquierdo disminuye una posición
11. luego si lado derecho diferente de lado izquierdo entonces auxiliar igual vector en la posición derecha, vector en la posición derecha igual al vector en la posición izquierda, y vector en la posición izquierda igual a auxiliar
12. luego si lado izquierdo igual a lado derecho mandamos el vector como este con la posicion de i y lo que tiene lado izquierdo menos 1
13. lado izquierdo mas 1 y el valor de la variable d todo esto hara que el vector inicial se ordene de forma correcta.
5. luego condicionamos que si lado izquierdo es mayor o igual al lado derecho entonces se debe retornar el vector
6. asignamos a i lo que tenga lado izquierdo y a d lo que tenga lado derecho
7. luego condicionamos que si lado izquierdo diferente de lado derecho entonces se crean pivote y auxiliar no obstante pivote se le asigna el lado izquierdo
8. luego asignamos el siclo while que pregunta si lado izquierdo diferente de lado derecho entonces se hace lo siguiente
9. otro siclo while que dice que el vector con la posición de lado derecho debe ser mayor e igual al vector en la posición de pivote y también que lado izquierdo debe ser menor que lado derecho, si esto se cumple entonces lado derecho disminuye una posición
10. en el siguiente while dice que si el vector en la posición izquierda es menor que el vector en la posición pivote y lado izquierdo menor que lado derecho entonces lado izquierdo disminuye una posición
11. luego si lado derecho diferente de lado izquierdo entonces auxiliar igual vector en la posición derecha, vector en la posición derecha igual al vector en la posición izquierda, y vector en la posición izquierda igual a auxiliar
12. luego si lado izquierdo igual a lado derecho mandamos el vector como este con la posicion de i y lo que tiene lado izquierdo menos 1
13. lado izquierdo mas 1 y el valor de la variable d todo esto hara que el vector inicial se ordene de forma correcta.
Acontinuacion mostraremos el
mismo código pero en Pseint
No existe "Return" en PSeInt.
Creo que el return se refiere a un leer
Me refiero a que en pseint a diferencia de por ejemplo python no tiene una función que haga de leer y imprimir (escribir)sólo se puede hacer por separado
Escribo auqi poque era mi informe final y no existe return :'v
PTMDR si vas a publicar algo haslo bien