Algoritmo: Bubble Sort

2/10
Recursos
Transcripci贸n

Aportes 36

Preguntas 1

Ordenar por:

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

o inicia sesi贸n.

鈥婤ubble Sort u Ordenamiento de Burbuja (Algoritmo m谩s simple que existe). Se le llama as铆 por que va seleccionando los elementos adyacentes, cambia el n煤mero que est谩 en la posici贸n incorrecta a la posici贸n correcta. Es un Algoritmo super lento y poco eficiente, primero por que necesitas dos bucles y segundo, por la cantidad de iteraciones del mismo.

Bubble Sort
La Ordenaci贸n de burbuja funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambi谩ndolos de posici贸n si est谩n en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten m谩s intercambios, lo cual significa que la lista est谩 ordenada.

Pseudoc贸digo Bubble Sort:

PROCEDIMIENTO bubble_sort ( vector a[1:n])
iteraci贸n 鈫 0
REPETIR
    permut 鈫 FALSO
    PARA i VARIANDO DE 1 HASTA n - 1 - iteraci贸n HACER
        SI a[i] > a[i+1] ENTONCES
            intercambiar a[i] Y a[i+1]
            permut 鈫 VERDADERO
        FIN SI
    FIN PARA
    iteraci贸n 鈫 iteraci贸n + 1
MIENTRAS QUE permut = VERDADERO

Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran peque帽as 鈥burbujas鈥.

Es el ordenamiento m谩s simple, y funciona validando cada elemento de la lista que a ordenar con el siguiente, es decir, realiza el intercambio de posici贸n en caso de que est茅n en orden err贸neo. El ordenamiento de burbuja (Bubble Sort) revisa varias veces el recorrido hasta que no se requieran m谩s intercambios, es decir, ya est谩 ordenado por completo. Aqu铆 podemos ver el recorrido del ordenamiento Bubble Sort

La nueva intro muy bonita por cierto!
En la universidad en la materia de Estructura de datos recuerdo que vi este metodo, lo supe implementar pero hoy dia no recuerdo a ciencia cierta como fue.
Asi que me servira mucho volverlo a ver.

Es importante entender el algoritmo de forma visual antes poder realizar su implementaci贸n.

Es el algoritmo de ordenamiento m谩s simple que existe
Va seleccionando dos n煤meros juntos y los cambia de posicion en caso del que la izquierda sea mayor, sino los deja igual y se mueve una posici贸n a la derecha, es un algoritmo muy lento porque necesitas dos bucles uno que recorre todos los datos y el otro que hace el cambio de datos en caso de ser encesario.

Bubble sort

  • Bubble sort (ordenamiento burbuja) es un m茅todo bastante sencillo e intuitivo de ordenar datos. Es muy 煤til para comenzar a comprender las formas en las que podemos ordenar la informaci贸n, aunque dada su complejidad no es muy 煤til en casos muy demandantes.
    Para poder entender c贸mo funciona el algoritmo, usaremos el conjunto desordenado de datos 7, 9, 3, 4, 8 y definiremos como
    N
    la cantidad de datos a ordenar, en este ejemplo
    N
    =
    6
    .

  • La forma en la que funciona el algoritmo del Bubble sort es utilizando intercambios. Por ejemplo, si queremos ordenar los datos de forma creciente, sabemos que hemos de dejar al principio (lado izquierdo) los valores m谩s peque帽os. Entonces vamos 鈥渢omando鈥 pares de datos y dejando del lado izquierdo el valor m谩s peque帽o. Para esto intercambiamos las posiciones de los dos elementos en cuesti贸n, y dejamos en la posici贸n de la izquierda el valor m谩s chico, y en el de la derecha el m谩s grande.

Mi humilde aporte:

Devuelve lo siguiente:

Solo con la pura explicaci贸n basta para decir que ese algoritmo es super lento y poco eficiente

3 Etapas del Algoritmo: Entrada, Proceso, Salida.

import random

def ordenamiento_de_burbuja(lista):
n = len(lista)

for i in range(n):
    for j in range(0, n - i - 1): # O(n) * O(n) = O(n * n) = O(n**2)

        if lista[j] > lista[j + 1]:
            lista[j], lista[j + 1] = lista[j + 1], lista[j]

return lista

if name == 鈥main鈥:
tamano_de_lista = int(input('De que tamano sera la lista? '))

lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
print(lista)

lista_ordenada = ordenamiento_de_burbuja(lista)
print(lista_ordenada)

El Bubble Sort b谩sicamente es un switch de arr[i] y arr[i+1] cuando arr[i] sea mayor que arr[i+1] para ordenar una lista

Buena clase vamos por mas.

Aunque es un algoritmo super sencillo de implementar, es poco eficiente comparado con otros. Pero es b谩sico de entender super bien, para luego entender los pr贸ximos algoritmos

Bubble sort:
Como si fuese una burbuja que va empujando el valor mas alto hacia el final de la lista

Interesante!

Mi primer m茅todo de ordenamiento que vi en programaci贸n, me recuerda la escuela.

Ordenamiento burbuja, es muy lento ya que tiene que hacer 2 ciclos uno para todo el recorrido y otro para hacer la comparaci贸n, esto es poco eficiente porque tiene que hacer muchos ciclos, por lo que no es recomendado

Que buena explicaci贸n

Muy simple en realidad.

Muy buena el video que muestra como funciona el Bubble Sort.

BUBBLE SORT
Ordenamiento en burbuja. Es de lento procesamiento, porque analiza n煤mero por n煤mero y repite el array hasta que quede ordenado.

<h3>Algoritmo: Bubble Sort</h3>

Es el algoritmo de ordenamiento m谩s simple que existe. Va seleccionado de 2 en 2 los elementos y de estos los pone en el orden correcto.

Este algoritmo es super lento, ya que nesesitas dos ciclo, el que recorre del primer elemento al 煤ltimo, y el que se encarga de que cada paso del recorrido haga el cambio.

Es un Algoritmo lento ya que necesita 2 ciclos para realizar el ordenamiento.

Excelente clase.

Esto tambien se da en el curso de POO orientado a python del profe David

El Bubble sort, es un algoritmo muy ineficiente, debido a que con un array mediano, se tendr谩n m谩s problemas que corrigeir y por tanto mayor tiempo.

Tenemos que tener dos bucles para que nos funciones el bubble sort

El bubble sort, es uno verdaderamente el algoritmo de ordenamiento que abre la introducci贸n a estos, debido a lo simple que 茅s.

El ordenamiento burbuja
.
El ordenamiento burbuja hace m煤ltiples pasadas a lo largo de una lista. Compara los 铆tems adyacentes e intercambia los que no est谩n en orden. Cada pasada a lo largo de la lista ubica el siguiente valor m谩s grande (o m谩s chico) en su lugar apropiado. En esencia, cada 铆tem 鈥渂urbujea鈥 hasta el lugar al que pertenece.
.

Algoritmo de ordenamiento. Burbuja(Bubble Sort en ingl茅s) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambi谩ndolos de posici贸n si est谩n en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten m谩s intercambios, lo cual significa que la lista est谩 ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran peque帽as burbujas. Tambi茅n es conocido como el m茅todo del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparaci贸n, siendo el m谩s sencillo de implementar.

El procedimiento de la burbuja es el siguiente: 搂 Ir comparando desde la casilla 0 n煤mero tras n煤mero hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevar谩 hasta la 煤ltima casilla, si no es as铆, ser谩 reemplazado por uno mayor que 茅l. 搂 Este procedimiento seguir谩 as铆 hasta que haya ordenado todas las casillas del vector. 搂 Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

Dado un vector a1, a2, a3, 鈥 an 1) Comparar a1 con a2 e intercambiarlos si a1>a2 (o a12) 2) Seguir hasta que todo se haya comparado an-1 con an 3) Repetir el proceso anterior n-1 veces
Algoritmo: Complejidad for(i=0; i < n-++){ T(n2)

for(j=0; j < n-1; j++){ T(n)
if(vec[j] > vec[j+1]){ T(1)
aux=vec[j]; T(1)
vec[j]=vec[j+1]; T(1)
vec[j+1]=aux;} T(1)
} }

Pseudoc贸digo Bubble Sort:

PROCEDIMIENTO bubble_sort ( vector a[1:n])
iteraci贸n 鈫 0
REPETIR
    permut 鈫 FALSO
    PARA i VARIANDO DE 1 HASTA n - 1 - iteraci贸n HACER
        SI a[i] > a[i+1] ENTONCES
            intercambiar a[i] Y a[i+1]
            permut 鈫 VERDADERO
        FIN SI
    FIN PARA
    iteraci贸n 鈫 iteraci贸n + 1
MIENTRAS QUE permut = VERDADERO```

La Ordenaci贸n de burbuja (Bubble Sort en ingl茅s) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambi谩ndolos de posici贸n si est谩n en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten m谩s intercambios, lo cual significa que la lista est谩 ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran peque帽as 鈥渂urbujas鈥. Tambi茅n es conocido como el m茅todo del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparaci贸n, siendo uno de los m谩s sencillos de implementar.

https://es.wikipedia.org/wiki/Ordenamiento_de_burbuja

Cuando yo implemente mi primer algoritmo de ordenamiento de tipo bubble sort yo use tres bucles:

  1. Para saber si los n煤meros estaban en orden
  2. Para recorrer el bucle
  3. Para cambiar los numero o letras en caso de que est茅n desordenados

Bubble Sort es un algoritmo no recomendado ya que tiene como 鈥淏ig-O鈥 (n^2) lo cual hace que su rendimiento sea bajo y que consuma muchos recursos, se le asigna el n^2 ya que para que este sea posible, se tiene que iterar un for dentro de otro for.

Aqu铆 una pagina con mas informaci贸n que incluye el gif de su representaci贸n
https://brilliant.org/wiki/bubble-sort/

Se agradece la explicaci贸n visual del algoritmo