Neste tutorial, você aprenderá como funciona a classificação por bolha. Além disso, você encontrará exemplos funcionais de classificação por bolhas em C, C ++, Java e Python.
A classificação por bolha é um algoritmo que compara os elementos adjacentes e troca suas posições se eles não estiverem na ordem pretendida. A ordem pode ser crescente ou decrescente.
Como funciona a classificação por bolha?
- Começando com o primeiro índice, compare o primeiro e o segundo elementos. Se o primeiro elemento for maior do que o segundo elemento, eles serão trocados.
Agora, compare o segundo e o terceiro elementos. Troque-os se não estiverem em ordem.
O processo acima continua até o último elemento.
Compare os elementos adjacentes - O mesmo processo continua para as iterações restantes. Após cada iteração, o maior elemento entre os elementos não classificados é colocado no final.
Em cada iteração, a comparação ocorre até o último elemento não classificado.
A matriz é classificada quando todos os elementos não classificados são colocados em suas posições corretas.
Compare os elementos adjacentes 
Compare os elementos adjacentes 
Compare os elementos adjacentes
Algoritmo de classificação de bolhas
bubbleSort (array) para i rightElement trocar leftElement e rightElement final bubbleSort
Exemplos de Python, Java e C / C ++
Python Java C C ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Classificação de bolha otimizada
No código acima, todas as comparações possíveis são feitas, mesmo se a matriz já estiver classificada. Aumenta o tempo de execução.
O código pode ser otimizado pela introdução de uma variável extra trocada. Após cada iteração, se não houver troca, não há necessidade de realizar mais loops.
Nesse caso, a variável trocada é definida como falsa. Assim, podemos evitar novas iterações.
Algoritmo para classificação de bolha otimizada é
bubbleSort (array) swapped <- falso para i rightElement trocar leftElement e rightElement trocados <- true end bubbleSort
Exemplos de classificação de bolha otimizada
Python Java C C + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if 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 BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Complexidade
Bubble Sort is one of the simplest sorting algorithms. Two loops are implemented in the algorithm.
| Cycle | Number of Comparisons |
|---|---|
| 1st | (n-1) |
| 2nd | (n-2) |
| 3rd | (n-3) |
| … . | … |
| last | 1 |
Number of comparisons: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2 nearly equals to n2
Complexity: O(n2)
Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n = n2
Time Complexities:
-
Worst Case Complexity:
O(n2)
If we want to sort in ascending order and the array is in descending order then, the worst case occurs. -
Best Case Complexity:
O(n)
If the array is already sorted, then there is no need for sorting. -
Complexidade média de caso: ocorre quando os elementos da matriz estão em ordem desordenada (nem crescente nem decrescente).
O(n2)
Complexidade do espaço: a
complexidade do espaço ocorre O(1)porque uma variável extra de temperatura é usada para a troca.
No algoritmo otimizado, a variável trocada aumenta a complexidade do espaço, tornando-o assim O(2).
Aplicativos de classificação por bolha
A classificação por bolha é usada nos seguintes casos, onde
- a complexidade do código não importa.
- um código curto é o preferido.
