Clase 9 de 10 • Curso de Introducción a los Algoritmos de Ordenamiento
Contenido del curso
Iván Arcos
Kenyi Julberht Hancco Quispe
Leonardo Galindo
Edwin Jesset Barrientos Gonzales
Royer Guerrero Pinilla
Elisa Zamarron Muñoz
Jaime Escobedo Vargas
Orlando Javier Javier Rosas
Cristian Blandon
Rubén Cuello
Jesús Petrona Castro
Juan Camilo Noreña López
Gerson Montenegro
Nahim Terrazas Parada
Juan Carlos Ortiz Romero
Hanier Morales
marco antonio
Michael Ballesteros
Joel Dominguez Merino
German Tellez Vanegas
Rafael Pardo Rodriguez
Javier Daza
José manuel Sanchez Juarez
Duban Andres Guzman Higuita
Juan Camilo Noreña López
Nicolas Alpargatero
Ian Yared Oliva Hernández
Pablo Eduardo Diaz Hernandez
Jhon Freddy Tavera Blandon
Este es el comportamiento de los algoritmos de ordenamiento en una imagen :D
Se suponía que Selection era más rápido que Bubble :O
Segun mis pruebas el Selection Sort es mas rapido que el Bubble Sort con diferencia. . . .
La notación Big-O nos proporciona una manera de saber cómo se va a comportar un algoritmo en función de los argumentos que le pasemos y la escala de los mismos.
Quería mostrar un gif de la velocidad de los algoritmos pero no fue posible team platzi deberían mejorar eso 😥😥😥, de todas formas les dejo el link Velocidad de algoritmos de ordenamiento
Es interesante, porque en ese GIF parece que gana BubbleSort.
Estos métodos son de orden O(n^2) y no exponenciales
"Polinomiales"
Gracias. Me estaba molestando escuchar tan seguido la palabra "exponencial"
Si se analiza a detalle ambos códigos nos daremos cuenta que tanto el Bubble Sort como el Selection Sort tienen casi la misma estructura de código, dos for anidados con un if dentro del segundo for, ahora bien, ambos algoritmos van ordenando el set en cada recorrido, ejemplo: si se ordena de menor a mayor en el caso del Bubble Sort los extremos derechos ya se consideran ordenados (números mayores) y ya no los analiza, y para el Selection sort el extremo izquierdo se considera ordenado y también ya no se analizan, la gran diferencia entre cada uno de ellos es que el Bubble Sort realiza muchos más cambios o swap entre cada recorrido y el Selection Sort sólo realiza uno en cada recorrido del set.
Otra diferencia sin duda, es que si el set de números ya está ordenado o semi-ordenado, el Selection Sort va a realizar todos los ciclo sin excepción, y en cambio para el Bubble Sort se puede implementar la verificación y saber si el set ya está ordenado y romper los ciclos y así terminar el algoritmo.
Se puede decir que depende del objetivo y uso que se le quiera dar, pero en definitiva ambos algoritmos son malos para ordenar set de números muy grandes.
Saludos.
Hola Jesús!
Tanto en buble sort como en selection sort se puede implementar la logica para que cuando este ordenado se haga un break y deje de ejecutar el ciclo.
Obtuve esta comparación luego de testar con 100, 1000, y 10000 valores a ordenar en cada oportunidad. Me pareció genial lo rápido que es Selection Sort, a pesar de que también usa un segundo ciclo.
Aquí el código
import random, timeit from bokeh.plotting import figure, output_file, show def selectionSort(array): for i in range(len(array)): auxIndex = i for j in range(i + 1, len(array)): if array[auxIndex] > array[j]: auxIndex = j array[i], array[auxIndex] = array[auxIndex], array[i] return array def bubbleSort(array): n = len(array) for i in range(n): for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] return array def createValues(size): return [random.randint(0, size) for i in range(size)] def createLoop(limit): loopLimit = limit baseSize = 100 values = [] times = {} for i in range(0, loopLimit): values = createValues(baseSize) startTime = timeit.default_timer() bubbleSort(values.copy()) stopTime = timeit.default_timer() finalTime = stopTime - startTime times[f'B={baseSize}'] = finalTime startTime = timeit.default_timer() selectionSort(values.copy()) stopTime = timeit.default_timer() finalTime = stopTime - startTime times[f'S={baseSize}'] = finalTime baseSize *= 10 return times def createColumnsPlot(values): x_vals = [] y_vals = [] for d in values: x_vals.append(f'{d}') y_vals.append(values[d]) output_file('comparing_plot.html') fig = figure(x_range=x_vals, plot_height=350, title="Time comparing: Bubble Sort VS Selection Sort", toolbar_location=None, tools="") fig.vbar(x=x_vals, top=y_vals, width=0.9) fig.y_range.start = 0 show(fig) if __name__ == "__main__": data = createLoop(3) createColumnsPlot(data)
Que basura de curso, pense que iban a ensenhar algoritmos como QuickSort o MergeSort, decepcionado totalmente
El Bubble Sort como el Selection Sort tienen casi la misma estructura de código, dos for anidados con un if dentro del segundo for, ahora bien, ambos algoritmos van ordenando el set en cada recorrido, ejemplo: si se ordena de menor a mayor en el caso del Bubble Sort los extremos derechos ya se consideran ordenados (números mayores) y ya no los analiza, y para el Selection sort el extremo izquierdo se considera ordenado y también ya no se analizan, la gran diferencia entre cada uno de ellos es que el Bubble Sort realiza muchos más cambios o swap entre cada recorrido y el Selection Sort sólo realiza uno en cada recorrido del set. Otra diferencia sin duda, es que si el set de números ya está ordenado o semi-ordenado, el Selection Sort va a realizar todos los ciclo sin excepción, y en cambio para el Bubble Sort se puede implementar la verificación y saber si el set ya está ordenado y romper los ciclos y así terminar el algoritmo.
Investigacion bien chingona guardado cuatro y media am.docx xD jajajaja crack!!
es verdad le toma el doble de tiempo
En java:
import java.util.Arrays; //1. Buscar el número menor en mi array //2. Crear dos subArrays para llevar el control de mi algoritmo //3. Imprimir el resultado del ordenamiento. public class SelectionSort { //Ciclo que recorre todo el array y busca el valor mínimo static void selectionSort(int[] numeros){ int n = numeros.length; for (int i = 0; i < n-1; i++) { int numMenor=i; for (int j = i+1; j < n; j++) { if (numeros[numMenor] > numeros[j]){ numMenor=j; } } int temp = numeros[i]; numeros[i] = numeros[numMenor]; numeros[numMenor] = temp; System.out.println("El Array como está quedando es: " + Arrays.toString(numeros)); } } public static void main(String[] args) { int[] numeros = {20, 5, 21, 6, 23, 7, 34, 999, 68}; selectionSort(numeros); System.out.println("El array ordenado es: " + Arrays.toString(numeros)); } }
Interesante el tiempo que les toma a cada algoritmo ordenarlos.
¿Por qué se coloca una coma al final?
Hola German, es que parte del codigo preguntas sobre la coma?
A lo mejor la prone al final de algunas partes, por ejemplo cuando termine unos parentesis. (), Algo asi, si preguntas por eso, esta mal, pudo haberse equivocado.
Yo también me pregunto lo mismo. El por qué de la coma al final del último for
Creo que el profesor todo lo ase todo a fuerza bruta todos los lenguajes de programación puede generar número aleatorio de una forma sencilla.
Por un momento pensé que mi laptop estaba pidiendo auxilio corriendo los programas jaja
Para que se usa "%d" % ? si ejecuto el codigo con o sin esto, me da el mismo resultado
Con el filtro en bubble de parar cuando quede ordenado, queda más rápido que el selection sort.
Para visualizar en la misma terminal los resultados y sin tener que alterar los scripts previamente realizados, hice otro script importando los dos scripts realizados previamente.
import SelectionSort,BubbleSort,datetime #dejare la lista con pocos valores aquí en el aporte de la clase por fines practicos lista=[2385,1853,5145,1102,5432,7367,3396,7513,3260,2428,3521,11663,2697,3102,3857] tiempoInicial = datetime.datetime.now() BubbleSort.bubbleSort(lista) print(datetime.datetime.now()-tiempoInicial, "fue el tiempo para Bubble Sort") tiempoInicial = datetime.datetime.now() SelectionSort.selectionSort(lista) print(datetime.datetime.now()-tiempoInicial, "fue el tiempo para Selection Sort")
El resultado se ve de la siguiente manera:
## Este es un programa que ordena elementos mediante el algoritmo SelectionSort import sys def SelectionSort(array): #recorremos nuestro array for i in range(len(array)): #Encontrar el valor minimo restante dentro de nuestro array desordenado idxDes = i print(array) for j in range(i+1, len(array)): if array[idxDes] > array[j]: idxDes = j array[i], array[idxDes] = array[idxDes], array[i] #Encontramos el minimo, vamos a moverlo al subarray arreglado array = [64, 25, 12, 22, 11] SelectionSort(array) print ("Sorted array") for i in range(len(array)): print("%d" %array[i]), <code>
Los dos algoritmos tienen un crecimiento del tipo, exponencial y este crecimiento, pese a que los dos son poco eficientes porque estamos enfocados en algoritmos muy simples
