Programa C++ para clasificación de burbujas

Bubble Sort es el algoritmo de clasificación más simple que funciona intercambiando repetidamente los elementos adyacentes si están en el orden incorrecto. Este algoritmo no es adecuado para grandes conjuntos de datos, ya que su complejidad de tiempo promedio y en el peor de los casos es bastante alta.

¿Cómo funciona la clasificación por burbujas?

Considere una array arr[] = {5, 1, 4, 2, 8}

Primer pase: 

• La ordenación de burbujas comienza con los dos primeros elementos, comparándolos para verificar cuál es mayor.
  • ( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), Aquí, el algoritmo compara los dos primeros elementos y los intercambia desde 5 > 1. 
  • ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Intercambiar desde 5 > 4 
  • ( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), Intercambiar desde 5 > 2 
  • ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), Ahora, dado que estos elementos ya están en orden (8 > 5), el algoritmo no los intercambia.

Segundo pase: 

• Ahora, durante la segunda iteración debería verse así:
  • ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 
  • ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Intercambiar desde 4 > 2 
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

Tercer Pase: 

• Ahora, la array ya está ordenada, pero nuestro algoritmo no sabe si está completa.
• El algoritmo necesita un pase completo sin ningún intercambio para saber que está ordenado.
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

Ilustración:

Las siguientes son las implementaciones de Bubble Sort. 

// C++ program for implementation 
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;
  
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
    int i, j;
    for (i = 0; i < n - 1; i++)
  
        // Last i elements are already 
        // in place
        for (j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}
  
// Function to print an array 
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
  
// Driver code
int main()
{
    int arr[] = { 5, 1, 4, 2, 8};
    int N = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, N);
    cout << "Sorted array: \n";
    printArray(arr, N);
    return 0;
}
// This code is contributed by rathbhupendra

// Optimized implementation of Bubble sort
#include <bits/stdc++.h>
using namespace std;
  
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   bool swapped;
   for (i = 0; i < n-1; i++)
   {
     swapped = false;
     for (j = 0; j < n-i-1; j++)
     {
        if (arr[j] > arr[j+1])
        {
           swap(arr[j], arr[j+1]);
           swapped = true;
        }
     }
  
     // IF no two elements were swapped 
     // by inner loop, then break
     if (swapped == false)
        break;
   }
}
  
// Function to print an array 
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout <<" "<< arr[i];
}
  
// Driver program to test above functions
int main()
{
    int arr[] = {5, 3, 1, 9, 8, 2, 4, 7};
    int N = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, N);
    cout <<"Sorted array: \n";
    printArray(arr, N);
    return 0;
}
// This code is contributed by shivanisinghss2110