Programa C para clasificación de burbujas: clasificación de burbujas en C

Introducción

La clasificación de una matriz ocupa un lugar de inmensa importancia en la informática. Su utilidad se nota cuando existe la necesidad de ordenar los datos en un orden específico. Hay diferentes tipos de algoritmos de clasificación. El algoritmo de clasificación más común y ampliamente utilizado es Bubble Sort.

Clasificación de burbujas en C

La técnica que se utiliza para ordenar en Bubble sort es simple y fácil de entender. Todo lo que hace es comparar el elemento actual con el siguiente elemento y cambiarlo si es mayor o menor según lo dicte la condición. El algoritmo es muy preciso. Cada vez que se compara un elemento con otros elementos hasta encontrar su lugar, se llama pase.

Este algoritmo es comparable a las burbujas en el agua, ya que filtra la parte superior de las burbujas en forma de matriz. Entre todos los algoritmos utilizados para clasificar, Bubble sort es el más fácil y el más lento con una complejidad de tiempo de O(n^2). Sin embargo, el algoritmo se puede optimizar mediante el uso de una variable indicadora que sale del bucle cuando se completa el intercambio. El mejor caso para la ordenación de burbujas puede ser O(n) cuando se ordena la matriz.

Por ejemplo, tomemos una matriz desordenada de cinco números como se indica a continuación

13, 32,26, 34,9

Bubble sort comenzará considerando los dos primeros elementos y los comparará para comprobar cuál es mayor. En este caso, 32 es mayor que 13. Entonces esta porción ya está ordenada. A continuación, comparamos 32 con 26. Entonces encontramos que 32 es mayor que 26, por lo que deben intercambiarse. La nueva matriz se verá como

13, 26, 32,34,9

A continuación, comparamos 32 y 34. Sabemos que ya están ordenados. Por lo tanto, pasamos a las dos últimas variables 34 y 9. Dado que 34 es mayor que 9, deben intercambiarse.

Intercambiamos los valores y llegamos al final de la matriz después de la primera iteración. Ahora la matriz se verá como

13, 26. 32,9,34

Después de la segunda iteración, la matriz se verá como

13, 26, 9,32,34

Después de la tercera iteración, la matriz se convertirá en

13,9,26,32,34

Después de la cuarta iteración, la matriz se ordenará por completo

9, 13,26,32,34

Debe leer: Ideas de proyectos en C

el algoritmo

Aquí estamos asumiendo que la matriz tiene n elementos. Además, asumimos que la función de valores de intercambio está intercambiando todos los valores para hacer que los números de la matriz estén ordenados.

iniciar BubbleSort (matriz)

para todos los elementos de la lista

si matriz[i]> matriz[i+1]

valores de intercambio (arreglo[i], arreglo[i+1] )

terminara si

fin para

matriz de retorno

fin de clasificación de burbuja

Leer: Clasificación en la estructura de datos: categorías y tipos

pseudocódigo

Es evidente en el algoritmo anterior que hay una comparación entre cada par de elementos de la matriz hasta que toda la matriz se ordena en orden ascendente. Puede dar lugar a algunos problemas de complejidad, como el resultado del algoritmo cuando la matriz ya está ordenada en orden ascendente. Para solucionar el problema, usaremos una variable de bandera, que nos permite ver si ha habido algún intercambio. Si no se necesita más intercambio, saldremos del bucle interno.

El pseudocódigo para el algoritmo BubbleSort se puede escribir de la siguiente manera

procedimiento BubbleSort (matriz: elementos en la matriz)

iterar= array.contar;

para k=0 para iterar-1 hacer:

bandera = falso

para l=0 para iterar-1 hacer:

si (matriz[l]> matriz[l+1]) entonces

valores de intercambio (matriz [l], matriz [l+1])

bandera = verdadero

terminara si

fin para

Si (no intercambiado) entonces

Descanso

Terminara si

Fin para

Matriz de retorno de procedimiento final

Probemos un programa de muestra de tipo burbuja en C :

# include<stdio.h>

vacío principal

{

matriz int [10], i, j, número

para (i=0; i<=9; i++)

{

scanf(“%d”, &arreglo[i])

}

para(i=0;i<=9;i++)

{

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

{

si(matriz[j]>matriz[j+1])

{

numero= matriz[j];

matriz[j]=matriz[j+1];

arreglo[j+1]=numero;

}

}

}

printf(“La matriz ordenada es /n”);

para(i=0;i<=9;i++)

{

printf(“%d”,&matriz[i])

}

}

Como se muestra en el ejemplo, este algoritmo de clasificación de burbujas acepta 10 números del usuario y los almacena en la matriz. En la siguiente parte, hay dos bucles for. El bucle exterior se ejecuta para el valor I, igual a cero a menos de nueve. La función del bucle externo es ocuparse de todos los elementos del valor que deben compararse con otros elementos.

Hay otro bucle dentro del bucle exterior. Comienza desde j=0 y corre hasta que sea menor o igual a ocho. En el interior, hay una instrucción condicional if que compara y verifica si el arreglo [j] es mayor que el arreglo [j+1]. Si se cumple la condición, los valores de array[j] y array [j+1] se intercambian entre sí.

Para este propósito se utiliza una variable con el nombre de num. Primero array[j] se asigna a num, luego array[j+1] se asigna a array[j], y finalmente num se asigna a array[j+1]. Este proceso continuará hasta que todos los elementos de la matriz se clasifiquen en orden creciente. Después de eso, se imprime la matriz ordenada.

Implementación optimizada de Bubble Sort

Tenemos un algoritmo optimizado para la clasificación de burbujas para mejorar los resultados. El uso de una variable de bandera hace la optimización. La variable de bandera mantendrá 1 si hay un intercambio, de lo contrario, saldrá del bucle. A continuación se muestra el programa optimizado de clasificación de burbujas en C.

#include<stdio.h>

vacío principal

{

int array [10], i, j, num, flag=0;

para (i=0; i<=9; i++)

{

scanf(“%d”, &arreglo[i])

}

para(i=0;i<=9;i++)

{

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

{

si(matriz[j]>matriz[j+1])

{

numero= matriz[j];

matriz[j]=matriz[j+1];

arreglo[j+1]=numero;

bandera=1;

}

si (! bandera)

{

descanso;

}

}

}

printf(“La matriz ordenada es /n”);

para(i=0;i<=9;i++)

{

printf(“%d”,&matriz[i])

}

}

El programa dado se ejecuta de una manera similar al programa normal de clasificación de burbujas. El único cambio es el uso de la variable flag. Inicialmente, el indicador se establece en 0. Sin embargo, si se produce un intercambio, el indicador se convierte en 1. Esto implica que la matriz aún requiere una verificación más. Por otro lado, si el indicador no es 1, lo que implica que no se ha producido el intercambio, salimos del ciclo interno, asumiendo que la matriz ya está ordenada. Una vez ejecutado, obtendremos el mismo resultado que el Bubble sort normal.

Complejidad del tiempo

La complejidad de tiempo en el mejor de los casos para la ordenación de burbujas es O(n). Ocurre cuando la matriz ya está ordenada. El peor de los casos es O(n*n) cuando la matriz no se ha ordenado.

Leer: Los 12 mejores programas de patrones en Java que debería consultar hoy

¿Qué sigue?

Si está interesado en obtener más información sobre Java, desarrollo de software de pila completa, consulte el Diploma PG de upGrad & IIIT-B en desarrollo de software de pila completa, que está diseñado para profesionales que trabajan y ofrece más de 500 horas de capacitación rigurosa, más de 9 proyectos. , y asignaciones, estado de ex alumnos de IIIT-B, proyectos finales prácticos y asistencia laboral con las mejores empresas.