Algoritmo Quicksort en Python: Implementación y Funcionamiento

Clase 34 de 42 • Curso Práctico de Estructuras de Datos y Algoritmos

Resumen

Para esta clase aprenderemos a reordenar una serie de números mediante quick sort, que no es más que un algoritmo de divide y vencerás, nuestro algoritmo se dividirá en 3:

Necesitamos dividir nuestro data set
Obtener un punto pivotal
Recursivamente ordenar cada mitad de mí array

Para este ejercicio utilizaremos Python por lo mucho que nos ahorra de código, tú sabes que podemos realizar los algoritmos sin importar el lenguaje de programación

Luis Gerardo Colmenares

student•

La funcion "particion" esta muy mal explicada. Cuantos lenguajes tengo que conocer para llevarle el hilo a este curso?

Xavier Alberto Garcia Navarro

student•

Pues yo te recomendaria el curso de programacion basica para que entiendas un poco la sintaxis del codigo en general y te des una idea mediante la logica de como se traduce un lenguaje a otro, recuerda que los lenguajes son un 80% parecidos y se diferencian por un 20%.

Xavier Alberto Garcia Navarro

student•

De igual manera puedes buscar ejemplos de estas estructuras de datos en youtube en el lenguaje que prefieras.

Oswaldo Javier Yugsi Yugsi

student•

Este video debería ser rehecho. Está muy mal explicado. Cuando el profesor empieza con la función quickSort dice más de una vez que aún no ha implementado las líneas de código que hacen el ordenamiento de las posiciones en el Array, cuando esas líneas están declaradas en la función partición.

Se nota mucho que está leyendo el código de a lado y que no viene con las tareas hechas.

Jecsham Castillo

student•

Mira la clase completa.

Oswaldo Javier Yugsi Yugsi

student•

La he visto. Y mantengo mi comentario.

Juan Castro

teacher•

Algoritmo de QuickSort en JavaSript :sunglasses:: Implementing Quicksort in JavaScript - Medium

David Santiago González Ramos

student•

Me has salvado, estoy agradecido. Porque con la clase quede re perdido.

Joel Vicente Nieto Gómez

student•

Excelente recurso, gráficamente explicado lo que va sucediendo en cada iteración.

Francisco Velasco

student•

Hasta aca un poco perdido.. no veo lo básico del curso

Omar Alejandro Barbosa Olivares

student•

Lo peor de esto, es que ni el profesor se toma el tiempo de venir a revisar los comentarios...

Luis Gerardo Colmenares

student•

He tenido varias dudas a lo largo del curso y ni una me ha respondido.

Xavier Alberto Garcia Navarro

student•

Para eso estamos nosotros, camarrada ;)

Walter Alvarado

student•

aquí una comparación animada entre quicksort y merguesort https://www.youtube.com/watch?v=es2T6KY45cA

Mauricio Gomez

student•

Excelente video, mucha gracias!

Moisés Manuel Morín Hevia

student•

Que grafico ! Gracias.

Miguel Angel Guante Suero

student•

https://www.youtube.com/watch?v=DYmTpUfcyT8

Explicacion grafica.

Carlos Enrique Ramírez Flores

student•

Excelente y es español!

David Barreto

student•

Excelente aporte, sin estos aportes no hubiese podido avanzar!

Brayan Ccari

student•

Para lo que aun tengan dudas de como funciona Quicksort, les comparto un video donde lo podran ver visualmente, y a mas detalle. A mi me ayudo muchisimo complementar con este contenidoQuickSort Visualization

David Santiago González Ramos

student•

Gracias por el video!! Me hizo entender cómo funciona el algoritmo... Sin embargo la verdad aún no lo entiendo bien en el código.

Anthony Smith Quispe De la cruz

student•

Muchas gracias por compartir el vídeo, me ayudo bastante a entender como funciona el algoritmo.

David Santiago González Ramos

student•

La verdad, muy difícil de entender la clase y por ende cómo implementar el algoritmo

Fernando Vladimir Gualan Camacho

student•

explicación muy pobre en esta clase, siendo un tema importante en este curso

Miqueas Gamero

student•

Buenas. Me tomé el trabajo de traducir una muy buena explicación de GeeksforGeeks

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6 

low = 0, high =  6, pivot = arr[h] = 70
Inicializa índice para primer elemento, i = -1

Recorre los elementos desde j hasta high -1
j = 0 : Como arr[j] <= pivot, hace i++ e intercambia(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // No hay cambios → i = j
                              

j = 1 : Como arr[j] > pivot, no hace nada
// No hay cambio en i y arr[]

j = 2 : Como arr[j] <= pivot, hace i++ e intercambia(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 

j = 3 : Como arr[j] > pivot, no hace nada
// No cambia en i y arr[]

j = 4 : Como arr[j] <= pivot, hace i++ e intercambia(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Como arr[j] <= pivot, hace i++ e intercambia(arr[i], arr[j]) 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped 

Salimos fuera del loop porque j es igual a high -1 
Finalmente ponemos el pivot en la posición correcta intercambiando
arr[i+1] y arr[high] (o pivot) 
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 y 70 intercambiados 

Ahora 70 está en el lugar correcto. Todos los elementos más pequeños que
70 están antes de él y los más grandes después.

Andres David Peña Velandia

student•

def ordenar(not_ordened_list):
	if len(not_ordened_list) == 0:
		return []
	elif len(not_ordened_list) ==1:
		return not_ordened_list

	left = []
	right = []
	equals = []
	pivote = not_ordened_list[0]

	for n in not_ordened_list[1:]:
		if pivote > n:
			left.append(n)
		elif pivote < n:
			right.append(n)
		elif pivote == n:
			equals.append(n)

	return ordenar(left) + [pivote] + equals + ordenar(right)



def run():
	not_ordened_list = [
3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
	
	print('LISTA NO ORDENADA')
	print(not_ordened_list)
	ordened_list = ordenar(not_ordened_list)
	print('\nLISTA ORDENADA')
	print(ordened_list)



if __name__ == '__main__':
	run()```

Efraín Hernández García

student•

Que buen codigo, felicidades! me gustó mucho

Franco Bottazzi

student•

Una forma de elegir el pivote más eficiente es que, en vez de ser el primer o último elemento, el pivote sea la media entre tres elementos del vector. Por ejemplo, la media entre el primer elemento, el segundo y el del medio:

mid = (low + high)/2
pivot = (arr[low] + arr[high] + arr[mid])/3

Aaron Joel Limachi Quispe

student•

Cabe denotar también que la eficiencia de este algoritmo depende mucho del pivote que se elija.

Aldo Miguel Ortiz Parodi

student•

Estoy sumamente perdidoooo. En serio, si quería enseñar Algoritmos con Python debió detenerse a enseñar el lenguaje y cómo usarlo para ir explicando los algoritmos desde un inicio. El haber usado 3 lenguajes para un curso que dice ser básico sobre algoritmos es demasiado.

DAVID STEVEN BOCAREJO IBAÑEZ

student•

El profesor es muy bueno explicando teoría, pero siento que el código lo explica de una manera muy desordenada, que en lo personal me desubica enormemente.

Daniel Santiago Perez Ducuara

student•

En una de las clases anteriores creando un código en C para un algoritmo de ordenamiento ponía las variables en el programa sin haberlas declarado, me parece una práctica malísima. Me está decepcionando este curso.

Juan Castro

teacher•

:snake: Ciclo o Bucle for in en Python

William Andres Dussan Gonzalez

student•

Es normal que yo entienda codigo pero no sepa escribir codigo?

Fernando Andres Muñoz Suazo

student•

Considero que si, dado que los lenguajes de programación están pensados para poder ser comprendidos al leerlos, implementan un "lenguaje natural" lo más posible.

Ahora respecto a escribir código es más cuestión de pensamiento sistemático y lógico. Es muy importante entender como funciona el proceso en la vida real, para poder abstraerlo y crear el código. Si A es válido pasa a B, si el valor de B es "x" pasa a D, porque para C se ocupa un valor "y".

Una buena manera de comenzar es con pseudocódigo, y claro prácticar y prácticar.

Diego Forero

Team Platzi•

Si, la práctica va a hacer que tu puedes escribir código, lo primero que tienes que hacer es pensar en la forma lógica de solucionar el problema que tienes, luego de eso si intentar plasmarla en código. Todo es cuestión de práctica.

Guillermo Castaño Vèlez

student•

Lo siento, pero creo que Platzi tiene un problema cuando llama cursos "basico" o "introducción", si superamos programar en 3 lenguajes seguramente no estuviéramos tomando este curso.

Juan Manuel Otero Rey

student•

Tengo otra solución y al ver los comentarios decidí documentarla mejor para ver si arroja algo de luz sobre este algoritmo:

#importamos la libreria random que vamos a utilizar mas adelante
from random import randint

def quicksort(data):
    # Una lista con cero (0) o un (1) elementos esta ordenada por definicion, retornamos el dataset
    if len(data) <= 1: return data
    # Creamos tres arrays para almacenar nuestros datos en cajas diferentes, 
    # comparando estos datos con nuestro pivote
    smaller, equal, larger = [], [], []
    # Selecionamos nuestro valor pivote de forma aleatoria desde nuestro data set,
    # esto hace nuestro codigo mas legible 
    pivot = data[randint(0, len(data) -1)]

    # Iteramos sobre nuestro dataset
    for value in data:
        # si el valor es menor que nuestro numero pivote lo colocamos en smaller
        if value < pivot: 
            smaller.append(value)
        # si el valor es igual que nuestro numero pivote lo colocamos en equal
        elif value == pivot: 
            equal.append(value)
        # si no cumple ninguna de esta condiciones significa que es mayor, por lo que colocamos el valor el larger
        else: 
            larger.append(value)
    
    # Ordenamos de forma recursiva, concatenando los resultados para ir ordenando nuestros datos.
    return quicksort(smaller) + equal + quicksort(larger)

Hollman Andres Barbon Florez

student•

Cordial saludo Juan Manuel

Gracias por documentar el código, es de gran ayuda, hay chance de aclarar un poco más está parte redondeada del siguiente código por favor, gracias.

Slds.

Juan Manuel Otero Rey

student•

Hola Andres, es muy simple, randint es una funcion de la libreria random.

Esta funcion retorna un numero aleatorio de un conjuto de parametros, los que usamos en este ejercicio son:

randint(low, high)

low = 0 -> numero que representa la minima cantidad a buscar high = len(data) ->funcion para saber el largo de un array - 1

(este menos uno se debe a que el array empieza en 0 y necesitamos saber es la ultima posicion excluyendo el 0, ya que este lo pasamos como parametro en low)

Luego el retorno de esta funcion es un entero el cual usamos como numero pivot dentro de nuestro array data[]

Luis Alfredo Villalta López

student•



def particion(arr, low, high):
    i = (low -1)
    pivot =  arr[high]

    for j in range(low, high):
        if arr[j]<= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i+1]

    arr[i+1], arr[high] =arr[high], arr[i+1]
    return (i+1)


def quickSort(arr, low, high):
    if low < high:
        pi = particion(arr, low, high)
        quickSort(arr, low, pi)
        quickSort(arr, pi+1, high)```