Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Comparación de algoritmos Bubble Sort y Selection Sort

9/10
Recursos

Aportes 34

Preguntas 2

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

Este es el comportamiento de los algoritmos de ordenamiento en una imagen 😄

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

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.

Estos métodos son de orden O(n^2) y no exponenciales

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)

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.

instala extensiones en code

  • Edit csv

  • Rainbow CSV

Hola a todos hice este codigo, esta seductor:

<code> 
def orden_1(x):
    y = x[:]
    box = []
    j = 0
    while j < len(y):
        if y[j] == min(y):
            box.append(y[j])
            y.remove(y[j])
            j = 0
        else:
            j += 1
            
#         print(len(y), j ,y, box)
    return(box)

Yo así hice mi comparación:

Hice uso de un decorador para el medir el tiempo de ejecución. Aquí el código:

from datetime import datetime

def execution_time(func):
    def wrapper(*args, **kwargs):
        initial_time = datetime.now()
        func(*args, **kwargs)
        final_time = datetime.now()
        time_elapsed = final_time - initial_time
        print(f'Pasaron {time_elapsed.total_seconds()} segundos')
    return wrapper

A mi me dio como resultado que Selection Sort era el mas rápido con el dataset proporcionado, la diferencia con un array pequeño prácticamente era 0

Que basura de curso, pense que iban a ensenhar algoritmos como QuickSort o MergeSort, decepcionado totalmente

No olviden quitar el print(array) antes de correr el programa 😂

Entiendo que el Insert sort es mas rapido deberian explicarlo

Muy interesante la información acerca del rendimiento de los algoritmos, con lo cual se pueden tomar decisiones en los desarrollos futuros a implementar.

Emocionante! se deberia dar mas cursos en relacion a un estudio profundo de otros algoritmos en Python!

Es muy interesante intentar hacer más eficiente el código cada vez.

gracias

SelectionSort >> 0:00:00.536935
BubbleSort >> 0:00:01.392604

aqui una comparacion de tiempos de ejecucioin de:

  1. ordenamiento por mzcla
  2. selection sort
  3. bubble sort
  4. sort que viene por defecto en python que es el mas rapido
    y el segundo mejor es el ordenamienzo por mezcla que hace uso de la programacion dinamica
import timeit
timeit.timeit('ordenamiento_por_mezcla(lista253)', number=10, globals=globals())
>>>0.2398644590011827
timeit.timeit('selection_sort(lista253)', globals=globals(), number=10)
>>>8.240095668999857
timeit.timeit('bubble_sort(lista253 )', globals=globals(), number=10)
>>>13.021493158001249
timeit.timeit('lista253.sort()', globals=globals(), number=10)
>>>0.0015169689995673252

Curiosamente en mi laptop el que se tardó más fue SelectionSort:

El coeficiente de la n, dentro del Big notation, es claramente la cantidad de ciclos que se tienen dentro de un algoritmo.

Siempre busca el tiempo de ejecución con Big O notation

No te guíes por el tiempo de ejecución puramente.

Crear simplicidad con Librerías, interesante

Interesantisimo, en mi PC el Buuble sort demoro un poco más del doble de tiempo que el Selection sort

Para evitar copiar información en el código, se puede estudiar cómo abrir, leer y cerrar archivos con información para el manejo de los datos.

![](
![](
![](