Ordenamiento de burbuja
Ordenamiento de burbuja es un algoritmo de clasificación que compara dos elementos adyacentes y los intercambia hasta que no están en el orden previsto.
Al igual que el movimiento de las burbujas de aire en el agua que suben a la superficie, cada elemento de la matriz se mueve hasta el final en cada iteración. Por lo tanto, se llama tipo de burbuja.
Trabajo de Bubble Sort
Supongamos que estamos tratando de ordenar los elementos en orden ascendente.
1. Primera iteración (comparar e intercambiar)
- A partir del primer índice, compare el primer y el segundo elemento.
- Si el primer elemento es mayor que el segundo elemento, se intercambian.
- Ahora, compare el segundo y el tercer elemento. Cámbialos si no están en orden.
- El proceso anterior continúa hasta el último elemento.
Compara los elementos adyacentes
2. Iteración restante
El mismo proceso continúa para las iteraciones restantes.
Después de cada iteración, el elemento más grande entre los elementos sin clasificar se coloca al final.
En cada iteración, la comparación tiene lugar hasta el último elemento sin clasificar.
La matriz se ordena cuando todos los elementos no ordenados se colocan en sus posiciones correctas.
Algoritmo de clasificación de burbujas
bubbleSort(array)
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
end bubbleSortCódigo de clasificación de burbuja en Python, Java y C/C++
Pitón
Java
C
C++
# Bubble sort in Python
def bubbleSort(array):
# loop to access each array element
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping elements if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
// Bubble sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// compare two adjacent elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call method using class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
// Bubble sort in C
#include <stdio.h>
// perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}
// Bubble sort in C++
#include <iostream>
using namespace std;
// perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size; ++step) {
// loop to compare array elements
for (int i = 0; i < size - step; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping elements if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}Algoritmo de clasificación de burbujas optimizado
En el algoritmo anterior, todas las comparaciones se realizan incluso si la matriz ya está ordenada.
Esto aumenta el tiempo de ejecución.
Para solucionar esto, podemos introducir una variable extra intercambiado. El valor de intercambiado se establece en verdadero si se produce un intercambio de elementos. De lo contrario, se establece falso.
Después de una iteración, si no hay intercambio, el valor de intercambiado estarán falso. Esto significa que los elementos ya están ordenados y no es necesario realizar más iteraciones.
Esto reducirá el tiempo de ejecución y ayudará a optimizar la clasificación de burbujas.
El algoritmo para la clasificación de burbuja optimizada es
bubbleSort(array)
swapped <- false
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
swapped <- true
end bubbleSortClasificación de burbuja optimizada en Python, Java y C/C++
Pitón
Java
C
C++
# Optimized Bubble sort in Python
def bubbleSort(array):
# loop through each element of array
for i in range(len(array)):
# keep track of swapping
swapped = False
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:
# swapping occurs if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swapped = True
# no swapping means the array is already sorted
# so no need for further comparison
if not swapped:
break
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
// Optimized Bubble sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < (size-1); i++) {
// check if swapping occurs
boolean swapped = false;
// loop to compare adjacent elements
for (int j = 0; j < (size-i-1); j++) {
// compare two array elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
// no swapping means the array is already sorted
// so no need for further comparison
if (!swapped)
break;
}
}
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call method using the class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}
// Optimized Bubble sort in C
#include
// perform the bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < size - 1; ++step) {
// check if swapping occurs
int swapped = 0;
// loop to compare array elements
for (int i = 0; i < size - step - 1; ++i) {
// compare two array elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted
// so no need for further comparison
if (swapped == 0) {
break;
}
}
}
// print array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main method
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}
// Optimized bubble sort in C++
#include
using namespace std;
// perform bubble sort
void bubbleSort(int array[], int size) {
// loop to access each array element
for (int step = 0; step < (size-1); ++step) {
// check if swapping occurs
int swapped = 0;
// loop to compare two elements
for (int i = 0; i < (size-step-1); ++i) {
// compare two array elements
// change > to < to sort in descending order
if (array[i] > array[i + 1]) {
// swapping occurs if elements
// are not in intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted
// so no need of further comparison
if (swapped == 0)
break;
}
}
// print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
// find the array's length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
} Complejidad de clasificación de burbujas
| Complejidad del tiempo | |
|---|---|
| Mejor | En) |
| El peor | En2) |
| Promedio | En2) |
| Complejidad espacial | O(1) |
| Estabilidad | Sí |
Complejidad en Detalle
Bubble Sort compara los elementos adyacentes.
| Ciclo | Número de comparaciones |
|---|---|
| 1º | (n-1) |
| 2do | (n-2) |
| 3ro | (n-3) |
| ……. | …… |
| ultimo | 1 |
Por lo tanto, el número de comparaciones es
(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2casi igual a n2
Por eso, Complejidad: En2)
Además, si observamos el código, la ordenación por burbujas requiere dos bucles. Por lo tanto, la complejidad es n*n = n2
1. Complejidades de tiempo
- Complejidad en el peor de los casos:
O(n2)Si queremos ordenar en orden ascendente y la matriz está en orden descendente, ocurre el peor de los casos.
- Complejidad del mejor caso:
O(n)Si la matriz ya está ordenada, entonces no hay necesidad de ordenar.
- Complejidad promedio del caso:
O(n2)Ocurre cuando los elementos de la matriz están desordenados (ni ascendentes ni descendentes).
2. Complejidad espacial
- La complejidad del espacio es
O(1)porque se utiliza una variable adicional para el intercambio. - En el algoritmo optimizado de clasificación de burbujas, se utilizan dos variables adicionales. Por lo tanto, la complejidad del espacio será
O(2).
Aplicaciones de clasificación por burbujas
La ordenación de burbujas se usa si
- la complejidad no importa
- Se prefiere código corto y simple.
Algoritmos de clasificación similares
- Ordenación rápida
- Tipo de inserción
- Ordenar por fusión
- Clasificación de selección
