Implementando QuickSort con Python

Sinceramente me parece que el video necesita mas explicacion y un ejemplo grafico de como funciona paso por paso el codigo, de igual forma les dejo aqui un video que les ayudara a entender mas el algoritmo https://www.youtube.com/watch?v=PgBzjlCcFvc

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

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.

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

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

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

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

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

Explicacion grafica.

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

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

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

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.

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

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

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.

• 🐍 Ciclo o Bucle for in en Python

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.

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.

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)

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

Primera parte, pero vamos con ánimo y persistir, nunca desistir.

# QuickSort Algorithm
# 1. Dividir el data set
# 2. Recursivamente orderar cada mitad

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

    # Por cada elemento del array
    for j in range( low, high ):
        # Si el elementos es menor al pivote
        # Mandarlo al lado izquiero (sorted)
        if arr[j] <= pivot:
            i++ # Track de hasta donde van sorteados
            arr[i], arr[j] = arr[j], arr[i] #Swap del siguiente que no lo estaba con el que encontro menor

    i++ #Aqui debe de ir el pivote
    
    #Swap del pivote con el punto donde debe estar (se declara sorteado)
    arr[i], arr[high] = arr[high], arr[i]
    return i #Regresar donde quedo el pivote ordenado    


def quickSort( arr, low, high ):
    if low < high:
        pi = particion( arr, low, high )
        quickSort( arr, low, pi ) # Ordenar lado izq
        quickSort( arr, pi + 1, high ) # Ordenar lado derecho ```

Veo que muchos tienen inconvenientes entendiendo como funciona y se hace un Quicksort, dejare la implementación del mismo en Javascript, comentado para poder ayudar a que lo comprendan un poco mejor:

Creo que faltó una explicación gráfica del algoritmo QuickSort antes de pasar a la implementación

La verdad este curso no me esta gustando nada, esta clase es un muy buen ejemplo de que no está bien preparado el material. Hay muchas cosas mejorables, los nombres de las variables, la sintaxis que usa, como acomoda el código y terrible la manera de explicar.

Yo lo implementé asi, el codigo del profe está bien, trate de hacerlo lo más conciso que pude, espero te guste y nunca pares de aprender.

def quick_sort(array):
	if len(array) <= 1:
		return array
# Escojo el valor del array que está aproximadamente en la mitad.
# Use list comprehension para hacer el codigo más corto, pero para quien no conoce el concepto les dejo un comentario abajo con el equivalente.⬇️
	pivot = array[len(array) // 2] 
	left_arr = [elemento for elemento in array if elemento < pivot ]
	# Capturo el elemento que es igual al pivot
	mid = [elemento for elemento in array if elemento == pivot ]
	right_arr = [elemento for elemento in array if elemento > pivot ]
	
	return quick_sort(left_arr) + mid + quick_sort(right_arr)

print(quick_sort([23,36,78,90,-1]))
#Output [-1,23,36,78,90]
# Este es el comentario que te decia 😁
# Equivalente a:
#   left_arr = []
#   for elemento in array:
#       if elemento < pivot:
#           left_arr.append(elemento) 

Embarrada que el profe diera por hecho que con la representación inicial cubría también la explicación gráfica del Dynamic Programming son con decir “y los combina en uno y en el otro no”. En estos momentos lo estoy confundiendo con BinarySearch. Pero bueno profundizar.

Código en cpp:

#include <iostream>
using namespace std;

int partition(int arr[], int start, int end) {

    int pivot = arr[start];

    int count = 0;
    for (int i = start + 1; i <= end; i++) {
        if (arr[i] <= pivot)
            count++;
    }

    // Giving pivot element its correct position
    int pivotIndex = start + count;
    swap(arr[pivotIndex], arr[start]);

    // Sorting left and right parts of the pivot element
    int i = start, j = end;

    while (i < pivotIndex && j > pivotIndex) {

        while (arr[i] <= pivot) {
            i++;
        }

        while (arr[j] > pivot) {
            j--;
        }

        if (i < pivotIndex && j > pivotIndex) {
            swap(arr[i++], arr[j--]);
        }
    }

    return pivotIndex;
}

void quickSort(int arr[], int start, int end)
{

    // base case
    if (start >= end)
        return;

    // partitioning the array
    int p = partition(arr, start, end);

    // Sorting the left part
    quickSort(arr, start, p - 1);

    // Sorting the right part
    quickSort(arr, p + 1, end);
}

int main()
{

    int arr[100] = {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};
    int n = 100;

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Mi ejemplo con TS

function quickSort (array: number[]): number[] {
  if(array.length < 2) return array
  let pivot: number = array.at(-1) ?? 0 
  
  const leftArray: number[] = []
  const rightArray: number[] = []
  
  for(e of array) {
    if (e < pivot) leftArray.push(e)
    if (e > pivot) rightArray.push(e)
  }
  
  return [...quickSort(leftArray), pivot, ...quickSort(rightArray)]
}

Algo raro hubo en esta clase, la calidad de la explicación disminuyó de forma dramática, creo que hubiera preferido mil veces un video de 12:50 explicando el algoritmo y que dejara como tarea el implementarlo.

Esto que se hizo en esta clase pude haberlo encontrado facilmente con una busqueda en DuckDuckGo, pero la explicación es lo que le hubiera dado un valor.

La verdad le falta detalle en la explicación y no hubo una introducción visual de como funciona este algoritmo.

Por si les sirve mi código. Al ejecutarlo, si le ponen ./quickSort -verbose les explica paso a paso: https://github.com/santiago-perez-03/sorting-algorithms/tree/main/quickSort

Además, recomiendo éste video que me sirvió para entenderlo bien: https://www.youtube.com/watch?v=eqo2LxRADhU

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

Que brujeria es esta, no necesitas una variable auxiliar en Python, herejias jajaja 😛

A darle!!

function quickSort(array) {
if (array.length < 1) {
return [];
}

var left=[];
var right=[];
var pivot=array[0];

for (var i = 1; i < array.length; i++) {
if (array[i]< pivot){
left.push(array[i]);
}
else {
right.push(array[i]);
}
}

return[].concat(quickSort(left),pivot,quickSort(right));
}
console.log(quickSort([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]));

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

Algunas cosas cambian pero aun es entendible. he estado perdiendo el miedo.

Encontré una muy buena visualización aquí!

La funcion quicksort utiliza una estructura en el algoritmo muy similar al merge sort, si se ve el algoritmo de merge sort la primera funcion que se lee de arriba abajo es la funcion principal donde se llena el arreglo y hace el llamado a la funcion de division.
Ya alli esa funcion de division da los valores a low, high alli hay que tener en cuenta que low no necesariamente es la priemra pocision del arreglo y high tampoco es necesariamente la ultima pocision del arreglo porque en esa funcion lo que hace la recursividad es dividr y guardar temporalmente el valor por lo que el low puede ser la mitad o high sea el valor de la mitad segun divida el arreglo.
la ultima funcion de Mergesort, realiza la union de los arreglos y los ordena.
En quick sort esta estructura se crea y se explica de abajo para arriba primero la de particion luego la de ordenamiento y luego la principal
El pivot es como el med en el algoritmo de Merge

Versión en JavaScript

//Divide the dataset
//Pivot point to compare
//Order each half of the array with recursion

const quickSort = (arr) =>{
    //Evaluate if the array is empty
    if(arr.length < 1){
        return [];
    }

    let left = [];
    let right = [];
    let pivot = arr[0];
    
    //Start in 1 because the pivot is the first element
    for(let i = 1; i < arr.length; i++){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }

    //We need a empty array because the first element that we are going to concatenate is an array
    return [].concat(quickSort(left), pivot, quickSort(right));
}

console.log(quickSort([5, -2, 0, 1, 10, 8, -9]))

La idea es entender el algoritmo y utilizando la recursividad manipulando los elementos de la función partición he entendido como hacerlo, es algo nuevo que no sabia de la programacion.

Acá les dejo el código en JavaScript en caso de que a alguien se le haga mas simple entenderlo en ese lenguaje.

function quicksort(array){
  var resultado = [];
  var izquierda = [];
  var derecha = [];
  const pivot = array [0];

  if(array.length<2){return array};

  for (var i = 1; i < array.length;i++){
    if(array[i]<pivot){
      izquierda.push(array[i]);
    } else{
      derecha.push(array[i]);
    }
  }

  return resultado.concat(quicksort(izquierda), pivot, quicksort(derecha))
}

Muchas gracias a los que estudian activamente y aportan para complementar las clases.

Las clases en las Universidades, o en Platzi, son una guía para aprender nada más.

Por si no les queda claro el concepto del QuickSort
![](

![](

def quick_sort(array):# ej: se recibe el array [5,6,4]
    result = [] # Se define el array que almacenará el resultado final
    
    # Cuando el arreglo a ordenar tenga solo un registro no se organiza y se retorna tal cual
    if(len(array)<1): 
        return result

    # Se usara el primer valor del array como punto de comparación
    pivot = array[0] # ejp: pivot = 5
    """ se van acompara cada uno de los valores con el primer valor (pivot) 
    los menores se va al arrglo de la izquierda y los mayore al arreglo 
    de la derecha """
    left = []
    right = []

    for i in range(1, len(array)):
        if(array[i] < pivot):
            left.append(array[i])#left = 4
        else:
            right.append(array[i])# right = 6

    """ se unen todos los arreglos, tener encuanta que pivot es un valor númerioc
    por lo tanto se debe pasar como arreglo para unir con los otros. """
    result = left+[pivot]+right # ejp: [4,5,6]
    return result


print(quick_sort([95,24,39,5,-9,-87,154]))

Python: Lenguaje de ultra alto nivel.

Esta explicación está muy compleja acá dejo una explicación superficial pero simple y una explicación mucho más detallada y super explicada.

explicación básica en computerphile
explicación completa

Una comparación entre mergesort y quicksort
Una discusión sobre en algoritmo usar en diferentes escenarios

Comparto el codigo un tanto optimizado en js. La particularidad de este metodo es que devuelve un array ordenado sin alterar el original.

const QuickSort = (array) =>{

    if(array.length < 1){
        return [];
        // validacion de que array ingresado por parametro esta ok
    }

    let pivot = array[0];
    let left = [];
    let right = [];

    for(let i=1; i<array.length; i++){

        if(array[i] < pivot){
            left.push(array[i]);
        } 
        else{
            right.push(array[i]);
        }
        
    }
    return [].concat(QuickSort(left), pivot, QuickSort(right))  //sera recursivo hasta que este todo ordenado
}

let array = [3, 2, 4, 1, 9, 5, 0, -1];
let arrOrdenado = QuickSort(array)

console.log(arrOrdenado)

Esta página les ayudará a entender mejor este algoritmo

Si hay algo que tengo que reconocer respecto a este curso, es que tuve que investigar los temas por mi cuenta como en ningún otro.

Cuando el profesor dice “Tu ia sabes”, yo nunca se xD

Este video me parece una muy buena explicación: https://www.youtube.com/watch?v=eqo2LxRADhU

Más o menos comprensible

Para entender Quicksort y las diferentes formas de particionar.
Algorithm Quicksort