Estaría super un curso enfocado a BIG O
Introducción
Introducción al curso y bienvenida
Bubble Sort
Algoritmo: Bubble Sort
Diseño y análisis de Bubble Sort
Configuración de Entorno
Implementación de Bubble Sort
Selection Sort
Algoritmo: Selection Sort
Diseño y análisis de Selection Sort
Implementación de Selection Sort
Cierre
Comparación de algoritmos Bubble Sort y Selection Sort
Cierre del curso y próximos pasos
Crea una cuenta o inicia sesión
¡Continúa aprendiendo sin ningún costo! Únete y comienza a potenciar tu carrera
Diseño y análisis de Bubble Sort
3/10Recursos
¿Cómo funciona el algoritmo "Odd-Even Sort"?
El algoritmo "Odd-Even Sort" es uno de esos métodos de ordenamiento que nos sorprenden por su simplicidad y eficacia en contextos específicos. Su funcionamiento se basa en comparar y, si es necesario, intercambiar pares de elementos adyacentes para ordenar una lista. Aquí te explicaré de manera detallada cómo opera este algoritmo paso a paso y qué aspectos debes considerar.
¿Qué pasos sigue el algoritmo?
Para entender cómo trabaja el algoritmo, vamos a considerar un conjunto de números que queremos ordenar. Imagina que comenzamos con la siguiente secuencia: 5, 4, 1, 2, 7.
-
Comparación e intercambio:
- Comenzamos comparando el primer y el segundo elemento. Si el primero es mayor, se intercambian. Por ejemplo, si comparamos 5 y 4, como 5 es mayor, los intercambiamos para obtener: 4, 5, 1, 2, 7.
- Luego seguimos comparando de manera similar, moviéndonos de un par al siguiente hasta recorrer toda la serie.
-
Revisión completa de la secuencia:
- Después de cada pasada completa, revisamos nuevamente desde el principio para asegurar que todos los elementos estén en el correcto orden. Continuamos con esta serie de comparaciones hasta que todo el conjunto de elementos esté ordenado.
Ejemplo de ejecución
Para ilustrar cómo sucede esto en la práctica, observa el siguiente procesamiento:
Primera pasada:
- Comparamos 5 con 1 → Cambio → Resultado: 5, 1, 4, 2, 7
- Comparamos 5 con 4 → Cambio → Resultado: 1, 4, 5, 2, 7
- Comparamos 5 con 2 → Cambio → Resultado: 1, 4, 2, 5, 7
- No hay cambio necesario para 5 y 7.
Segunda pasada:
- La ejecución comienza nuevamente desde el inicio, repitiendo el proceso de comparación y cambio, hasta lograr una lista completamente ordenada: 1, 2, 4, 5, 7.
¿Cuál es su rendimiento?
Es importante entender el rendimiento de este algoritmo para evaluar su eficiencia:
- Complejidad temporal: El "Odd-Even Sort" tiene una complejidad temporal de
O(n²), dondenes el número de elementos en el conjunto. Esto significa que su rendimiento disminuye exponencialmente con un aumento de datos. - Estrategia de mejora: Si trabajas con grandes volúmenes de datos, considera opciones alternativas que tengan una complejidad más baja, como Quick Sort o Merge Sort, que pueden ofrecer un mejor rendimiento en tales circunstancias.
¿Cómo se visualiza su complejidad?
A medida que insertamos más datos en el algoritmo, el tiempo de ejecución se incrementa de forma cuadrática. Visualizar esta relación gráfica te ayudará a recordar cómo esta curva de ejecución se dispara con el aumento de datos: N representa el número de datos, y T el tiempo necesario para el procesamiento completo.
Por lo tanto, mientras más datos procese, este algoritmo se volverá cada vez más lento, lo que destaca la importancia de conocer más algoritmos para poder elegir el que mejor se adapte a cada situación.
En resumen, si bien "Odd-Even Sort" puede ser útil en ciertos casos, es esencial entender su limitación de rendimiento para evitar sorpresas inesperadas y optar por algoritmos más eficientes cuando sea necesario.
Aportes 35
Preguntas 4
Ordenar por:
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.
Bubble Sort en Java:
```java
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Intercambia si el elemento actual es mayor que el siguiente
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Array ordenado:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
```public class BubbleSort {
public static void bubbleSort(int\[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr\[j] > arr\[j + 1]) {
// Intercambia si el elemento actual es mayor que el siguiente
int temp = arr\[j];
arr\[j] = arr\[j + 1];
arr\[j + 1] = temp;
}
}
}
}
public static void main(String\[] args) {
int\[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Array ordenado:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
Bubble Sort en JavaScript:
```js
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Últimos i elementos ya están ordenados
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Intercambia si el elemento actual es mayor que el siguiente
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
// Ejemplo de uso
const array = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(array));
```function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Últimos i elementos ya están ordenados
for (let j = 0; j < n - i - 1; j++) {
if (arr\[j] > arr\[j + 1]) {
// Intercambia si el elemento actual es mayor que el siguiente
\[arr\[j], arr\[j + 1]] = \[arr\[j + 1], arr\[j]];
}
}
}
return arr;
}
// Ejemplo de uso
const array = \[64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(array));
La curva cuadrática es una parábola no una curva exponencial. La exponencial es “a” elevado a la “x” siendo “a” una constante!
buena introducción a Big O, después de este seguiré con ese curso.
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
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!!!
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?