Bienvenido al Curso

1

Introducci贸n al curso b谩sico de algoritmos y estructuras de datos

Introducci贸n a los algoritmos

2

驴Qu茅 entiende una computadora?

3

Lenguajes de programaci贸n

4

Estructuras de datos

5

驴Qu茅 es un algoritmo?

6

Metodolog铆a para la construcci贸n de un algoritmo

7

Variables y tipos de datos

8

User defined data types

9

Instalando Ubuntu Bash en Windows

10

Creando nuestro user defined data type

11

Abstract Data Types b谩sicos: Lists, Stacks, Queues

12

Explicaci贸n gr谩fica Data Types b谩sicos

13

Glosario de funciones para Abstract Data Types

14

Clases y objetos

15

Creando tu primera Queue: Arrays

16

Creando tu primera Queue: implementaci贸n.

17

Creando tu primera Queue: implementar la funci贸n enQueue

18

Creando tu primera Queue: implementar la funci贸n deQueue

19

Creando tu primera Queue: main code

Algoritmos de ordenamiento

20

Algoritmos de ordenamiento

21

Bubble sort

22

Bubble sort: implementaci贸n

23

Bubble sort: main code

24

Insertion sort

25

Desaf铆o: implementa un algoritmo de ordenamiento

Recursividad

26

Recursividad

27

La funci贸n Factorial, calculando el factorial recursivamente

28

Manejo de cadenas de caracteres

29

Arte: Generando arte recursivo

Divide and conquer y programaci贸n din谩mica

30

Divide and Conquer (divide y vencer谩s)

31

Qu茅 es la programaci贸n din谩mica (divide y vencer谩s v2.0)

32

MergeSort

33

Desaf铆o: Buscar el algortimo m谩s r谩pido de sort

34

Implementando QuickSort con Python

35

Implementando QuickSort con Python: main code

Algoritmos 'Greedy'

36

Qu茅 son los Greedy Algorithm

37

Ejercicio de programaci贸n greedy

38

Ejercio de programaci贸n greedy: main code

Grafos y 谩rboles

39

Grafos y sus aplicaciones

40

脕rboles

驴C贸mo comparar Algoritmos?

41

C贸mo comparar algoritmos y ritmo de crecimiento

驴Qu茅 sigue?

42

Cierre del curso y siguientes pasos

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Implementando QuickSort con Python

34/42
Recursos

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:

  1. Necesitamos dividir nuestro data set
  2. Obtener un punto pivotal
  3. 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

Aportes 58

Preguntas 6

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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 鈥減articion鈥 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

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.

Lo siento, pero creo que Platzi tiene un problema cuando llama cursos 鈥渂asico鈥 o 鈥渋ntroducci贸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.

Est谩 complejo

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 鈥測 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

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]));

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)

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 鈥淭u 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