Diseño y análisis de Bubble Sort

Estaría super un curso enfocado a BIG O

Les recomiendo este video, donde puede ver esta algoritmo un poco mas interactivo xd
https://www.youtube.com/watch?v=lyZQPjUT5B4

con JS

Genero un arreglo de 10 valores al azar y luego aplico el BubbleSort

function bubbleSort(arr) {
  if (arr.length === 0) {
    return arr;
  } else {
    let i, j;
    for (i = 0; i < arr.length - 1; i++) {
      for (j = 0; j < arr.length - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          let temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }
  return arr;
}

const numbers = new Array(10)
  .fill(0)
  .map(() => Math.floor(Math.random() * 11));
console.log(numbers);
console.log(bubbleSort(numbers));```

Big O notation es una increíble herramienta que nos ayuda a determinar la complejidad de un algoritmo dado que podemos medir su performance en cuanto al uso de espacio en disco, así como otros recursos (memoria uso de CPU, tiempo de ejecución, etc.,). Lo anterior nos ayuda a identificar el peor escenario donde el algoritmo llegue al punto más alto de exigencia.

Entre más datos proceses, más exigente se vuelve tu algoritmo…

n^2 no es exponencial 😦 es polinomial. 2^n si sería exponencial

Me gustaría dejar en claro que n^2 es una función cuadrática y por lo tanto es polinomial y NO es exponencial.
Ricardo comentó ese error en varias ocasiones en la lección y aunque seguramente solo fue una confusión simple y no afecta la implementación del algoritmo, si me parece que se debe aclarar esto sobre todo para poder calcular el performance (Big O) correctamente.

me encanto el ejemplo escrito manualmente y el grafico para darle mas entendimiento al algoritmo.

Dejaré esto por aquí y me iré lentamente 😃
https://platzi.com/clases/complejidad-js/

Big o notation: Mientras más grande sea el set de datos del algoritmo el tiempo de ejecución va a crecer de manera exponencial.

A la espera del curso se complejidad computacional.

El big o notation, se refiere al coeficiente que pone a prueba nuestros algoritmos y cómo estos, tienen un rendimiento en varios casos.

En el minuto con 53 segundo: dice que el “5” logrò posicionarse en la tercera posiciòn del array??¿ fue en la tercera posiciòn o en la segunda posiciòn. Los espacios en memoria comienzan en 0 o en 1? de ante mano muchas gracias.

Excelente explicacion.

Muy bien explicado!!
A pasar esto a código!!!

Bubble Sort hace uso de dos bucles o ciclos. El primero que está encargando de recorrer todo nuestro vector, y el segundo que se está encargando de ejecutar las comparaciones cada vez que se avanza.

Para los que les guste el lenguaje C aquí hay un ejemplo:
https://youtu.be/wuWnUn26Bs8

Profe estas re quebrado 😛

Complejidad de bubble sort

• Dado que estamos realizando N
  recorridos por cada dato y son N
  datos, entonces podemos decir que la complejidad del algoritmo de ordenamiento bubble sort es

O(n2)

• Recuerda que cuando hablamos de complejidad tomamos el peor de los casos posibles, y se “redondea” al factor que tiene la tasa de crecimiento mayor.

• Es sencillo notar que se pueden hacer algunas mejoras al algoritmo, se puede optimizar de varias maneras, de cualquier forma, para un caso muy grande, como
  100000
  de datos, obtendremos un desempeño muy cercano al

O(n2)

• Debido a esto, el algoritmo puede ser útil como explicación general de un algoritmo de ordenamiento, dado que es sencillo de entender y sencillo de codificar, pero resulta ser poco práctico para resolver problemas en los que se manejen grandes conjuntos de datos.

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.

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 en su lugar apropiado. En esencia, cada ítem “burbujea” hasta el lugar al que pertenece.

buen curso de introduccion a las estructuras de datos

La curva cuadrática es una parábola no una curva exponencial. La exponencial es “a” elevado a la “x” siendo “a” una constante!

Muy bien Explicado!!!

Me encanto, lo entendí a la perfección.

Genial.

Me molesta que diga que n^2 tenga un crecimiento exponencial, el crecimiento expoencial es mucho más rápido que cualquier potencia de n

Big o notation: A mayor datos mayor tiempo de ejecución

Que genial, es muy entendible la verdad.

Muy buena explicación. Más claro no puede ser ome.

Big O
El tiempo de exposición será cuadrático.

La notación Big O mide el tiempo de ejecución de los algoritmos en su peor caso.

Bubble Sort Ejemplo:

Excelente explicacion!!!