Python de clasificación rápida
Funciones y métodos de Python
Michael Zippo
01.11.2021
Un Python QuickSort selecciona un elemento pivote y divide los elementos de una matriz en dos matriz < em> s. Los n√∫meros más altos que el pivote van en una matriz ; los n√∫meros más bajos que el pivote van a otro. Cada matriz se ordena y luego todas las matriz s se fusionan en una.
Hay muchos algoritmos de ordenaciòn que puede utilizar para ordenar una lista en programaciòn. Hay Python ordenaciones de inserciòn , clasificaciones de burbujas y más. Los QuickSort son uno de los tipos más comunes.
En esta guìa, vamos a hablar sobre qué son los QuickSorts y còmo funcionan. Veremos un ejemplo de Python QuickSort para que pueda aprender a implementar uno.
Sin más preámbulos, ¬°comencemos!
¿Qué es Python QuickSort?
Un algoritmo Python QuickSort divide una matriz en submatrices. Este algoritmo llama a estas submatrices de forma recursiva para ordenar cada elemento de la lista. El contenido de una submatriz está determinado por un elemento pivote que no se mueve a una nueva submatriz.
El algoritmo QuickSort divide y conquista. Esto significa que la tarea de ordenar una lista se divide en varias subtareas. Al final de la clasificaciòn, los resultados de estas subtareas se unen para devolver una lista ordenada.
En un QuickSort, la subtarea establece un pivote para cada sublista y ordena los elementos seg√∫n su valor relativo a el pivote.
¿Cuándo deberìa usar un QuickSort de Python?
Un QuickSort es √∫til cuando la complejidad del tiempo importa. Esto se debe a que QuickSort usa menos espacio de memoria que otros algoritmos, lo que les da un aumento de eficiencia.
El 81% de los participantes afirmaron que se sentìan más seguros sobre sus perspectivas laborales después de asistir a un bootcamp. Asòciese a un bootcamp hoy mismo.
El graduado promedio de un bootcamp pasò menos de seis meses en la transiciòn profesional, desde comenzar un bootcamp hasta encontrar su primer trabajo.
Solo debe usar un QuickSort si está familiarizado con la recursividad de Python . Esto se debe a que el algoritmo QuickSort depende de funciones recursivas.
Un QuickSort es más eficiente que una ordenaciòn por combinaciòn en arreglos más peque√±os. Sin embargo, en conjuntos de datos más grandes, una ordenaciòn por inserciòn o una ordenaciòn por combinaciòn puede ser más rápida.
¿Còmo funciona un QuickSort?
Un QuickSort elige un elemento para que sirva como pivote. Puede ser cualquier elemento de una lista. Para este tutorial , vamos a elegir el √∫ltimo elemento de una lista (3).
Un QuickSort compara el valor de pivote con cada n√∫mero cuando recorremos los elementos de la lista. Si un elemento es mayor que el n√∫mero de pivote, movemos el n√∫mero después del pivote; de ‚Äã‚Äãlo contrario, movemos el n√∫mero antes del pivote:
El valor 3 se ha movido hacia abajo en nuestra lista. Todos los elementos de menos de 3 m oved a su izquierda; todos los valores mayores que tres se movieron a su derecha.
Nuestra matriz de Python se divide en dos mitades: elementos mayores que el pivote y elementos menos que un pivote.
Una vez que este proceso ha comenzado, comienza un nuevo pivote en cada una de las dos mitades. Este pivote comienza por separado y usa el mismo algoritmo que el anterior. Primero, estableceremos un valor de pivote que sea igual al √∫ltimo valor de cada lista:
A continuaciòn, moveremos todos los valores mayores que un pivote a la derecha del pivote. Movimos todos los valores menos que el pivote a la izquierda.
| Pivot One |
|
| Pivote dos |
|
|
| 1 | 2 |
| 4 | 8 | 5 |
Este proceso contin√∫a hasta que ordenamos nuestra lista:
| Primera vez | 1 | 2 |
| 4 | 8 | 5 |
| Segunda vez |
| < fuerte> 1 |
|
| 8 | 5 |
|
|
|
|
| 5 | 87t? / |
| Tercero Hora |
|
|
|
|
| 8 |
Nuestra matriz final se ve asì:
Ejemplo de Python QuickSort
QuickSort necesita dos funciones: una funciòn pivote y una funciòn QuickSort.
Comencemos con la funciòn de particiòn. Esto dividirá, o preparará, la matriz seg√∫n el valor del elemento pivote.
Nuestra funciòn de particiòn:
- Seleccionará el elemento pivote
- Mover todos los elementos más grandes que el pivote a la derecha del pivote
- Mover todos los elementos menos que el pivote a la izquierda del pivote
Programa QuickSort Python
Vamos a escribir un programa que implemente este algoritmo:
Primero, seleccionamos un elemento pivote. Esto es igual al n√∫mero más alto de nuestra lista.
A continuaciòn, recorremos todos los elementos de la lista usando un Python for loop . Si un n√∫mero es menor que o igual al pivote, se mueve a la izquierda del pivote. De lo contrario, va a la derecha del pivote.
Nuestra funciòn Python devuelve el nuevo valor alto. El nuevo valor alto es igual al elemento + 1.
A continuaciòn, tenemos que ejecutar nuestro algoritmo. Podemos hacer esto escribiendo una funciòn separada:
"Career Karma entrò en mi vida cuando más lo necesitaba y rápidamente me ayudò a combinar con un bootcamp. ¬°Dos meses después de graduarme, encontré el trabajo de mis sue√±os que se alineaba con mis valores y metas en la vida! "
Venus, ingeniero de software en Rockbot
Esta funciòn comprueba si el valor de "bajo" es menor que el valor de "alto". Si es asì, nuestra clasificaciòn puede continuar. De lo contrario, nuestra clasificaciòn se detiene. Si nuestra clasificaciòn se detiene, significa que tenemos ordenò la lista.
A continuaciòn, nuestra funciòn llama al método prepare () . Esto identifica un puntero para el pivote y mueve los elementos a su lugar correcto.
Nuestra funciòn luego llama al método quick_sort () dos veces. La primera vez, ejecutamos QuickSort en los elementos a la izquierda del pivote. La segunda vez, ejecutamos QuickSort en los elementos a la a la derecha del pivote. Por lo tanto, nuestra funciòn es recursiva porque se llama a sì misma.
Esto contin√∫a hasta que todos los elementos de la lista están ordenados.
Escribiendo un método principal
Vamos a escribir un programa principal que defina una lista para rt:
Primero, especificamos una lista de valores para ordenar. Usamos el método Python len () para calcular la longitud de nuestra lista de valores. A continuaciòn, llamamos al método quick_sort () .
Pasamos "valores" como los n√∫meros que queremos ordenar. Luego pasamos 0 como el n√∫mero bajo. La longitud de los "valores" menos 1 es el valor alto que especificamos. El valor alto es la longitud de los valores menos 1 porque el primer elemento de una lista tiene el n√∫mero de ìndice 0.
Intentemos ejecutar nuestro programa:
Nuestro còdigo devuelve una lista ordenada. Lo hicimos. Date una palmadita en la espalda. QuickSort no es fácil de entender o implementar.
Descripciòn general de la complejidad
En promedio, este algoritmo funcionará en O (n * log n). Esto sucede cuando el elemento pivote no es el elemento más grande o más peque√±o y cuando el elemento pivote no está cerca del elemento central.
El QuickSort tiene el peor caso com flexibilidad de O (n2). Esto ocurre cuando el elemento seleccionado como pivote es el elemento más grande o el más peque√±o. Si este es el caso, el elemento pivote siempre estará al final de una matriz ordenada. Esto creará una serie de submatrices innecesarias.
La mejor complejidad de caso para este algoritmo es O (n * log n). Esto sucede cuando el elemento pivote es igual al elemento del medio o cerca del elemento del medio.
Para obtener más informaciòn sobre la complejidad del algoritmo, consulte nuestra guìa de Notaciòn Big O .
Conclusiòn
Python QuickSorts usa la recursividad para dividir una lista en listas más peque√±as que luego se ordenan. Cada lista se ordena en torno a un elemento pivote. Los elementos mayores que el pivote se mueven a su derecha; los elementos más peque√±os se mueven a la izquierda del pivote.
Para obtener orientaciòn sobre los principales recursos de aprendizaje, cursos en lìnea y libros de Python, lea nuestro completo Guìa de Còmo aprender Python .
