Cursos Empresas Blog Live Conf Eventos Precios

0:0012:50

Recursos

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

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Curso Práctico de Estructuras de Datos y Algoritmos

Clase 34 / 42

Ver clases

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Curso Práctico de Estructuras de Datos y Algoritmos

Clase 34 de 42

Clase 34 / 42

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Curso Práctico de Estructuras de Datos y Algoritmos

Clase 34 / 42

Ver clases

Comentarios

Luis Gerardo Colmenares#1178190

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

Oswaldo Javier Yugsi Yugsi#612591

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.

Juan Castro#522524

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

Francisco Velasco#802958

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

Omar Alejandro Barbosa Olivares#982506

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

Walter Alvarado#1093352

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

Miguel Angel Guante Suero#1135371

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

Explicacion grafica.

Brayan Ccari#819025

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

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.

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()```

#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)

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)```

Comentarios

Luis Gerardo Colmenares#1178190

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

Oswaldo Javier Yugsi Yugsi#612591

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

Juan Castro#522524

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

Francisco Velasco#802958

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

Omar Alejandro Barbosa Olivares#982506

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

Walter Alvarado#1093352

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

Miguel Angel Guante Suero#1135371

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

Explicacion grafica.

Brayan Ccari#819025

David Santiago González Ramos

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.

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()```

#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)

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)```

Comentarios (65)65 comentarios

Luis Gerardo Colmenares

Hace 7 años

Xavier Alberto Garcia Navarro

Hace 6 años

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%.

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

Oswaldo Javier Yugsi Yugsi

Jecsham Castillo

Mira la clase completa.

La he visto. Y mantengo mi comentario.

Juan Castro

Profesor

Hace 8 años

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

Joel Vicente Nieto Gómez

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

Francisco Velasco

Omar Alejandro Barbosa Olivares

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

Para eso estamos nosotros, camarrada ;)

Walter Alvarado

Mauricio Gomez

Excelente video, mucha gracias!

Moisés Manuel Morín Hevia

Que grafico ! Gracias.

Miguel Angel Guante Suero

Carlos Enrique Ramírez Flores

Excelente y es español!

David Barreto

Excelente aporte, sin estos aportes no hubiese podido avanzar!

Brayan Ccari

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

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

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

Fernando Vladimir Gualan Camacho

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

Miqueas Gamero

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

Andres David Peña Velandia

Efraín Hernández García

Que buen codigo, felicidades! me gustó mucho

Franco Bottazzi

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

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

Aldo Miguel Ortiz Parodi

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

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

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.

:snake: Ciclo o Bucle for in en Python

William Andres Dussan Gonzalez

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

Fernando Andres Muñoz Suazo

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

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

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

Hollman Andres Barbon Florez

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.

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

Recursos

Resumen

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Progreso del curso

Bienvenido al Curso

Introducción a los algoritmos

Algoritmos de ordenamiento

Recursividad

Divide and conquer y programación dinámica

Algoritmos 'Greedy'

Grafos y árboles

¿Cómo comparar Algoritmos?

¿Qué sigue?

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Recursos

Resumen

Comentarios

Recursos

Resumen

Comentarios