Comparación de algoritmos Bubble Sort y Selection Sort

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

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

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.

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.

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

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

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.

![](

![](

![](