Bubble sort

Dato Curioso:
En el año 2007, el ex CEO de Google, Eric Schmidt, le preguntó al candidato presidencial Barack Obama una vez durante una entrevista sobre la mejor manera de ordenar un millón de enteros, y Obama, haciendo una pausa por un momento, respondió: “Creo que el algoritmo de Bubble sort sería el camino equivocado”

Aqui les comparto el ejercicio de la clase

Array = [5,2,4,2,7]

Primer recorrido

	Iteracion #1: Index 0 con Index 1
		5 < 2 = False, hacemos cambio entre 5 y 2
		Array = [2,5,4,2,7]

	Iteracion #2: Index 1 con Index 2
		5 < 4 = False, hacemos cambio entre 5 y 4
		Array = [2,4,5,2,7]

	Iteracion #3: Index 2 con Index 3
		5 < 2 = False, hacemos cambio entre 5 y 2
		Array = [2,4,2,5,7]

	Iteracion #4: Index 3 con Index 4
		5 < 7 = True, no hacemos ningun cambio
		Array = [2,4,2,5,7]


Segundo recorrido

	Iteracion #5: Index 0 con Index 1
		2 < 4 = True, no hacemos ningun cambio
		Array = [2,4,2,5,7]

	Iteracion #6: Index 1 con Index 2
		4 < 2 = False, hacemos cambio entre 4 y 2
		Array = [2,2,4,5,7]

	Iteracion #7: Index 2 con Index 3
		4 < 5 = True, no hacemos ningun cambio
		Array = [2,2,4,5,7]

	Iteracion #8: Index 3  con Index 4
		5 < 7 = True, no hacemos ningun cambio
		Array = [2,2,4,5,7]

BUBBLE SORT: IMPLEMENTACIÓN
Es un algoritmo de búsqueda y uno de los mas simples. Este algoritmo funciona cambiando las celdas de los números en caso de que no estén ordenadas y va de par en par.
Debe quedar muy bien ordenado de mayor a menor, recordando que se repite el ciclo hasta que quede totalmente ordenado.
Excelente explicación, muchas gracias!!

Éstos son los pasos de la burbuja del ejercicio de hoy

1. [5, 2, 4, 2, 7]
   (5 <- 2)
2. [2, 5, 4, 2, 7]
   ***(5<-4)
3. [2, 4, 5, 2, 7]
   ******(5<-2)
4. [2, 4, 2, 5, 7]
   ***(4<-2)
5. [2, 2, 4, 5, 7]

es uno de los mas simples y fáciles de implementar pero es uno de los menos eficientes teniendo una complejidad de o(n^2) siendo su peor de los casos n*(n-1)/2

** Mi aporte con JavaScrip**

const bubbleSort = [7, 3, 5, 6, 8, 0, 4]

let bubbleSortF = (inputArr) => {
  let len = inputArr.length;
  let swapped;
  do {
      swapped = false;
      for (let i = 0; i < len; i++) {
          if (inputArr[i] > inputArr[i + 1]) {
              let tmp = inputArr[i];
              inputArr[i] = inputArr[i + 1];
              inputArr[i + 1] = tmp;
              swapped = true;
          }
      }
  } while (swapped);
  console.log(inputArr);
  return inputArr;
};

bubbleSortF(bubbleSort);

así se ve facil, quiero ver la implementación en código.

El algoritmo en python:

Recuerdo cuando mi profe de progra 2 nos pidio crear un algoritmo de nuestra imaginación para ordenar un arreglo, y al hacer mi propia implementación resulto que era exactamente igual a este 😄

Bubble sort, Es un algoritmo de ordenamiento rapido de implementar pero ineficiente para cantidad de datos grandes. Se ordena por pares y se va repitiendo de 1 a 1 hasta que queda totalmente ordenado, es muy iterativo y muy poco eficiente (por la cantidad de iteraciones)

Lo que entonces sucede, es que el va ordenando por cada uno de los indices del array los valores que posee hasta ordenarlos correctamente, por ejemplo:

array = [9, 2, 4, 5, 1]

primero compararia el 9 con el 2 y asi sucesivamente hasta ordenar todos los elementos del array```

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Mi aporte en JavaScript.
Se que no es la manera más corta pero fue totalmente desde cero 😄

Pizarrón de la clase:

mi propuesta para el bubble sort
![](

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void bubbleSort(int *arreglo,const short tam){
    short i,j;
    for(i = 0; i < tam; ++i){
        for(j = 0; j < tam -1; ++j){
            if(arreglo[j] > arreglo[j + 1]){
                arreglo[j] = arreglo[j] ^ arreglo[j + 1];
                arreglo[j + 1] = arreglo[j] ^ arreglo[j + 1];
                arreglo[j] = arreglo[j] ^ arreglo[j + 1];}}}}

void imprime (int *arreglo,const short dimencion){
    short i;
    for(i = 0;i <dimencion; ++i)
        printf(" %d |",arreglo[i]);
    printf("\n");}
int main(void)
{
    srand(time(NULL));
    short dimencion = 20;
    short i;
    int arreglo[dimencion];
    for(i = 0; i < dimencion; ++i)
        arreglo[i] = rand()%100+0;
    printf("Sin ordenar:\n\n");
    imprime(arreglo,dimencion);
    bubbleSort(arreglo,dimencion);
    printf("\n");
    printf("Ya ordenado:\n\n");
    imprime(arreglo,dimencion);
    return 0;
}

El Bubble sort nos servirá solo para entender un algoritmo relativamente sencillo, así poder pasar a estudiar otro con dificultad media, porque para grandes cantidades de informacion, no es eficiente.

El curso se ve largo, pero de verdad es muy bueno como profundiza los temas.

¡Genial! Entendí el algoritmo perfecto y lo realicé en JS.
Te lo comparto Platzinauta:

let numbers = [1,4,3,5,6,2,7,425,23,4,35,76,457,4,587,435,2352,35,123,4443,3,23,536,6754,7];

const bubbleSortAlgorithm = (arr) => {
    let sortedElementsCounter = 0;

    for (let position in arr) {
        let currentValue = arr[position];
        let adyacentValue = arr[parseInt(position) + 1];

        if (currentValue < adyacentValue){
            arr[position] = adyacentValue;
            arr[parseInt(position) + 1] = currentValue;
        }else{
            sortedElementsCounter++;
        }
    }

    if(sortedElementsCounter == arr.length) 
        return [arr, true];
    else
        return [arr, false];
}

const bubbleSort = (arr) => {
    let counterIteration = 0;
    let finalSortedArray = [];
    while(true){
        [arr, isSorted] = bubbleSortAlgorithm(arr);
        if(!isSorted){
            finalSortedArray = arr;
            counterIteration++;
        }else{
            return [finalSortedArray,counterIteration];
        }
    }
}

let [sortedNumbers, iterations] = bubbleSort(numbers);

console.log('Iterations:', iterations);
console.log(sortedNumbers);

Cualquier sugerencia es bienvenida 😊👌

• Buble Sort, ordena por pares de 1-1 y se va repitiendo hasta que este ordenado. Es sencillo pero poco eficiente cuando se tiene una gran cantidad de elementos a a comparar.

Bubble Sort es el algoritmo más simple que hay

Excelente explicación de la clase, muy clara la manera de explicar del profesor.

que buena explicación, excelente.

Buena esa.

Bien claro!

Claro el tema… vamos al </>

Es la mejor explicación de Bubble sort. Me quedó super claro

Entendido…

Este curso lo habias impartido como algoritmos con C? Creo haber estudiado esto antes xD

Fácil de entender pero como comentas es un algoritmo algo tardado jaja

Excelente explicación.

😃 en pocos minutos y ya aprendí un algoritmo

Aquí la solución en TypeScript:

estuvo muy fácil de entender

Con esta explicación es fácil de entender el método de ordenamiento Bubble sort. Muchas gracias.

Muy buen explicación

Excelente, ya me quedo más claro, y super bien explicado!

muchas gracias

En el Bubble sort, si se aplica un ordenamiento de menor a mayor, el elemento mayor siempre queda al final del vector desde el primer recorrido, y si es de mayor a menor, el elemento menor siempre queda al final del vector desde el primer recorrido, por lo cuál se puede decir que el último elemento está completamente ordenado, por lo cual en cada iteración se obtiene un elemento completamente ordenado, haciendo una mejora al algoritmo se puede evitar comparar los elementos completamente ordenados.

Metodo Burbujaaa 😃

Lo hice así, a ver cómo lo hace él en la siguiente clase…

#include <stdio.h>
  
#define SIZE 7

int array[SIZE], buffer;


void ordenar()
{
        for( int i = 0; i < SIZE; i++ )
        {
                for(int j = 0; j < SIZE; j++ )
                {
                        if( array[j] < array[j + 1] )
                        {
                                buffer = array[j];
                                array[j] = array [j + 1];
                                array[j + 1] = buffer;
                        }
                }
        }
}

int main( int argc, const char *argv[] )
{
        for( int i = 0; i < SIZE; i++ )
        {
                printf("ingrese un numero: ");
                scanf( "%d", &buffer );
                array[i] = buffer;
        }

        ordenar();

        for ( int i = 0; i < SIZE; i++)
        {
                printf("%d\n", array[i] );
        }

        return 0;
}```

#include <iostream>

using namespace std;
//bubble sort
int main ()
{
    int i, j, datos[5] = {2,5,1,7,9}, siguiente;
    for ( i = 0; i < 5; i++ )
    {
        for ( j = 0; j < 5; j++ )
        {
            siguiente = datos[j + 1];
            if ( datos[j] > siguiente )
            {
                datos[j + 1] = datos[j];
                datos[j] = siguiente;
            }
        }
    }
    for ( i = 0; i < 5; i++ )
    {
        cout << datos[i] << endl;
    }
}

C#

using System;
using System.Collections.Generic;
using System.Linq;



    class Class1
    {
         static void Main(string[] args)
        {


            int[] aray = { 1, 4, 5, 2, 8, 7, 6, 3, 9 };
            var variable = 0;
            for (var i = 0; i < aray.Length; i++)
            {
                for (var j = 0; j < aray.Length; i++)
                {
                    if (aray[i] > aray[i + 1])
                    {
                        variable = aray[i];
                        aray[i] = aray[i + 1];
                        aray[i + 1] = variable;
                    }
                }
            }

            

            Console.WriteLine(aray);

        }
    }

``

Me imagino que aunque sea el sort más básico, es aplicable en muy pocos casos.

Este es mi código propio luego de ver esta clase. Solo con el mecanismo en mente.

#include <stdio.h>
#include <string.h>
#define SIZE 5

int values[SIZE], cell = -1;
int firstCell;

void createBubble (int number)
{
  if(cell == -1)
  {
    cell ++;
  }
  values[cell] = number;
  cell++;
}

void swapValues(int *previous1, int *previous2)
{
  //This function swap values using a buffer
  //to temporarely allocate the value of an element
  int buffer = *previous1;
  *previous1 = *previous2;
  *previous2 = buffer;
}

void sort ()
{
  for (int i = 0; i < cell-1; i++)
  {
    if(values[i] > values[i+1])
    {
      swapValues(&values[i], &values[i+1]);
    }
  }
}

void printBubble ()
{
  printf("[");
  for (int i = 0; i < 5; i++)
  {
    printf("%d ", values[i]);
  }
  printf("]\n");
}

int main(int argc, char const *argv[]) {
  int goON;

  createBubble(1);
  createBubble(5);
  createBubble(3);
  createBubble(7);
  createBubble(4);

  printBubble();

  printf("Sort...\n");

  sort();
  sort();

  printBubble();

  return 0;
}

genial!! retroalimentandome 😉

++Bubble Sort: ++

El mas rápido
Muy iterativo
Poco Eficiente

Amigos, hice un ejemplo de Bubble Sort en donde se muestra cada uno de los aterradores
https://platzi.com/tutoriales/1469-algoritmos/9226-mi-ejemplo-de-bubble-sort/

acá les dejo dos links que pueden interesarles sobre como funciona el Bubble Sort Acá hay otro asegurence de bajarle el volumen antes de abrir el último que tiene el audio alto.

Ya quiero ver cómo se implementaría.