Kit Ciencia Y Arte: Ordenando Listas (Bubble Sort): 4 etapas

2024 Autor: John Day | [email protected]. Última modificação: 2024-01-30 11:38

En el mundo de las ciencias de la computación, sabre ordenar listas es como sabre escribir. Es una buena manera de ver como los algoritmos son una manera de hacer las cosas en um computador, y que la forma de hacer direta algo no es la mejor en um computador. Acá explico uno de los algoritmos más cnocidos de comutación que es el "Bubble Sort", y explicaré con detalle en que consiste

Este Instructable, consideraría que es AVANZADO, pero no hay nada como los retos difíciles, assim que não eres experto o experta no importa, haz el intento igual…

Etapa 1: ¿Ordenar Listas?

Hoy en día not the computer en all las cosas. Los teléfonos hoy en día son praticamente super computadoras. Mientras las computadoras toman datos, se construyen listas de datos. Uma lista de dados é um conjunto de dados como este:

{Tomás, Abraham Carolina, Matias, Maria, Marcela}

Es una lista de nombres. Ahora bien, en muchas ocasiones, necesitamos ordenarlos, es decir acomodar la lista en un orden particular, por ejemplo de mayor a menor ou vice-versa, ou en orden alfabético.

¿Porqué ordenarlos? Veja o exemplo da lista de nomes da imagem. Es una lista larga, si les pido busquen el nombre IRENE, en ¿cual list es más fácil? en la ¿ordenada verdad? bueno por eso mismo ordenar listas de dados es algo extremadamente importante em um computador, pera luego poder usar os dados de forma efectiva.

¿Cómo los ordeno? pasemos al siguiente paso

Passo 2: Algoritmo "Bubble Sort" Ordenamiento De Burbuja

Si tengo una lista de números, o nombres, ¿Cómo las puedo ordenar? Existen muchas maneras de hacerlo, acá les voy a explicar la que se llama "Bubble Sort", no es de las más rápidas, de hecho puede que sea de las peores, pero si es un buen ejemplo de como una idea se escribe como un algoritmo, y luego se escribe como un programa de computadora. Además, creo que ve super bonito no playground do circuito.

La Idea

La idea del Bubble Sort, es la de burbujas flotando, si ha dos burbujas y una es más grande que la otra, la más liviana pasa la más pesada, y así se van acomodando… es muy similar a tener una caja de piedras de diferentes tamaños, si las sacudo por suficiente tempo, las más pesadas se van al fondo e las livianas se quedan arriba.

El Algoritmo

Los pasos del algoritmos filho:

1. Tenemos uma lista de 1 a n elementos
2. Comenzar por el 1
3. Preguntar se o número na posição atual é o prefeito que el de la posição siguiente
4. Si es mayor cambiarlos, sino, dejarlos igual
5. Mover una posición
6. Si es el n, entonces marcar n-1 cómo el último y volver a 2
7. Sino, Volver a 3
8. Si el como marcado último es igual al primero, entonces terminar terminar

En Acción

Como ven um veces escribir un algoritmo es algoritmo confuso, por eso vean el video explico cual es el concepto y funcionamiento detrás del algoritmo con un ejemplo sencillo.

Etapa 3: Playground El Algoritmo En El Circuit

El Código básico

Veamos primeiro uma versão do algoritmo, sin agregarla nada de luces o sonido:

números de byte [9]; // Arreglo que contiene los numeros

int i, j; // Iteradores

// Algoritmo bubbleSort

void loop () {for (i = 0; i <= 9; i ++) {for (j = 0; j <= 9 - i; j ++) {if (números [j] <= números [j + 1]) {// mudança de posição de números float f = números [j]; números [j] = números [j + 1]; números [j + 1] = f; }}}}

Como ven primero creamos un arreglo de byte, en este caso lo llamamos numbers [9]. É um arreglo de 10 números (de 0 a 9), de numero tipo byte. Tambi'en creamos dos iteradores i y j. Estos son los que vana recorrer el arreglo.

En el loop principal, vean las línea:

para (i = 0; i <= 9; i ++) {para (j = 0; j <= 9 - i; j ++) {}}

Que i recorre todo el arreglo de 0 a 9. Dentro de esta j, noten como va de 0 a 9-i. Es decir, primero va de 0 a 9, luego de 0 a 9-1, luego de 0 a 9-2. Estamos porque como se ve no vídeo, por cada iteração sabemos que o último número já é o prefeito.

Dentro de esos iteradores, se hace la pregunta:

if (números [j] <= números [j + 1])

Es decir si el siguiente es menor o igual entonces debemos cambiarlo. Para cambiarlo hay that hacer un "swap" is decir tomar el valor del arreglo, guardarlo en uma variável temporal, atribuir el novo valor, y luego en temporal al la siguiente posición del arreglo. Vánlo en estas três linhas de código:

float f = números [j]; //temporal

números [j] = números [j + 1]; números [j + 1] = f;

Descargar el Circuit Playground

O código completo no Github, inclui todo o necesario para gerar um novo arreglo aleatório com números de 0 a 255, e para usar o numero como cantidad de rojo, para exibir os LEDs. Ustedes lo pueden modificar para que haga más cosas como sonidos, etc.

Etapa 4: Funcionando Y Reto

En el vídeo además le agregué sonido, eso se los dejo de reto a ustedes.

Retos

1. Agregar sonido
2. Programar otros algoritmos de ordenamiento (Quick Sort, Merge Sort)
3. Medir que tan rápido resuelve and arduino, colocando cada vez mais elementos en el arreglo y medir cuanto tarda, ¿Es lineal?