Clasificación por selección VS Clasificación por burbujas

No es una contribución válida En esto, cubriremos la comparación entre Selection Sort VS Bubble Sort. Los recursos requeridos por los algoritmos de Clasificación por Selección y Clasificación por Burbujas sobre la base de la Complejidad de Tiempo y Espacio son los siguientes. 

Time Complexity - Space Complexity - 

Profundicemos en el funcionamiento de estos algoritmos. 

Clasificación de selección : 
el algoritmo de clasificación de selección generalmente es el primer algoritmo de clasificación que se nos enseña. Aquí, en cada iteración del ciclo interno, el elemento más pequeño se reemplaza con el elemento inicial en cada ciclo. Después del final de cada ciclo, incrementamos la posición inicial en 1 y lo ejecutamos hasta el penúltimo elemento de la array. Por lo tanto, al hacerlo al final del ciclo externo, tendremos una array ordenada.

La siguiente imagen explica la iteración del algoritmo de clasificación de selección.  

Aquí podemos simplificar el algoritmo de clasificación por selección diciendo que la clasificación aquí se realiza sobre la base del elemento más pequeño al más grande. Primero se ordena el elemento más pequeño y luego el segundo elemento más pequeño y así sucesivamente. 

Implementación de la clasificación de selección: 

A continuación se muestra la implementación del algoritmo explicado anteriormente.

#include <iostream>
using namespace std;
void Selection_Sort(int arr[], int n) 
{
    for(int i = 0; i < n - 1; ++i) 
    {
        int min_index = i; 
        for(int j = i + 1; j < n; ++j) 
        {
            if(arr[j] < arr[min_index]) 
                min_index = j;
        }
        swap(arr[i], arr[min_index]); 
    }
}
int main()
{
    int n = 5;
    int arr[5] = {2, 0, 1, 4, 3};
    Selection_Sort(arr, n);
    cout<<"The Sorted Array by using Selection Sort is : ";
    for(int i = 0; i < n; ++i)
        cout<<arr[i]<<" ";
    return 0;
}

class GFG{
 
  static void Selection_Sort(int arr[], int n) 
  {
    for(int i = 0; i < n - 1; ++i) 
    {
      int min_index = i; 
      for(int j = i + 1; j < n; ++j) 
      {
        if(arr[j] < arr[min_index]) 
          min_index = j;
      }
      int temp = arr[i];
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int n = 5;
    int arr[] = {2, 0, 1, 4, 3};
    Selection_Sort(arr, n);
    System.out.print("The Sorted Array by using Selection Sort is : ");
    for(int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
  }
}
 
// This code is contributed by aashish1995

def Selection_Sort(arr, n):
     
    for i in range(n - 1):
        min_index = i 
         
        for j in range(i + 1, n):
            if (arr[j] < arr[min_index]):
                min_index = j
                 
        arr[i], arr[min_index] = arr[min_index], arr[i] 
         
# Driver Code
n = 5
arr = [ 2, 0, 1, 4, 3 ]
Selection_Sort(arr, n)
 
print("The Sorted Array by using " \
      "Selection Sort is : ", end = '')
for i in range(n):
    print(arr[i], end = " ")
     
# This code is contributed by SHUBHAMSINGH10

using System;
 
public class GFG{
 
  static void Selection_Sort(int []arr, int n) 
  {
    for(int i = 0; i < n - 1; ++i) 
    {
      int min_index = i; 
      for(int j = i + 1; j < n; ++j) 
      {
        if(arr[j] < arr[min_index]) 
          min_index = j;
      }
      int temp = arr[i];
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int n = 5;
    int []arr = {2, 0, 1, 4, 3};
    Selection_Sort(arr, n);
    Console.Write("The Sorted Array by using Selection Sort is : ");
    for(int i = 0; i < n; ++i)
      Console.Write(arr[i] + " ");
  }
}
 
// This code is contributed by aashish1995

<script>
 
// JavaScript program for above approach
 
    function Selection_Sort(arr, n)
  {
    for(let i = 0; i < n - 1; ++i)
    {
      let min_index = i;
      for(let j = i + 1; j < n; ++j)
      {
        if(arr[j] < arr[min_index])
          min_index = j;
      }
      let temp = arr[i];
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  }
 
// Driver Code
 
    let n = 5;
    let arr = [2, 0, 1, 4, 3];
    Selection_Sort(arr, n);
    document.write("The Sorted Array by using Selection Sort is : ");
    for(let i = 0; i < n; ++i)
      document.write(arr[i] + " ");
 
</script>

The Sorted Array by using Selection Sort is : 0 1 2 3 4 

Bubble Sort : 
el algoritmo de clasificación de burbujas puede parecer un poco confuso cuando lo estudiamos por primera vez. Pero aquí está la fácil explicación de ello. Aquí el intercambio se lleva a cabo de dos maneras. En cada iteración del ciclo externo, se encuentra el elemento más grande y se intercambia con el último elemento del ciclo. En el ciclo interno, intercambiamos por parejas dos elementos consecutivos. En cada ciclo interno, vamos del primer elemento al elemento menos que pasamos en el ciclo anterior. La siguiente imagen muestra la primera iteración del ciclo interno en el algoritmo de clasificación de burbujas.

Aquí podemos simplificar el algoritmo de clasificación de burbujas diciendo que la clasificación aquí se realiza sobre la base del elemento más grande al más pequeño . El elemento más grande se mantiene primero en la última ubicación de la array. Luego, el segundo elemento más grande en la penúltima ubicación y así sucesivamente.

Implementación de Bubble Sort: a 
continuación se muestra la implementación del algoritmo explicado anteriormente.

#include <iostream>
using namespace std;
void Bubble_Sort(int arr[], int n) 
{
    for(int i = 1; i < n; ++i)     
    {   
                for(int j = 0; j <= (n - i - 1); ++j)  
        {   
            if(arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]); 
        }
    }
}
 
int main()
{
    int n = 5;
    int arr[5] = {2, 0, 1, 4, 3};
    Bubble_Sort(arr, n);
    cout<<"The Sorted Array by using Bubble Sort is : ";
    for(int i = 0; i < n; ++i)
        cout<<arr[i]<<" ";
    return 0;
}

import java.io.*;
 
class GFG{
     
static void Bubble_Sort(int arr[], int n) 
{
    for(int i = 1; i < n; ++i)     
    {
        for(int j = 0; j <= (n - i - 1); ++j)  
        {   
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            } 
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5;
    int arr[] = { 2, 0, 1, 4, 3 };
     
    Bubble_Sort(arr, n);
     
    System.out.print("The Sorted Array by using Bubble Sort is : ");
    for(int i = 0; i < n; ++i)
        System.out.print(arr[i]+" ");
}
}
 
// This code is contributed by Shubhamsingh10

def Bubble_Sort(arr, n):
    for i in range(1, n):
        for j in range(0, n - i):
            if (arr[j] > arr[j + 1]):
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                 
    return arr
     
# Driver Code
n = 5
arr = [ 2, 0, 1, 4, 3 ]
arr = Bubble_Sort(arr, n)
 
print("The Sorted Array by using Bubble Sort is : ", end = '')
for i in range(n):
    print(arr[i], end = " ")
 
# This code is contributed by Shubhamsingh10

// C# program for the above approach
using System;
 
public class GFG{
     
    static void Bubble_Sort(int[] arr, int n) 
    {
        for(int i = 1; i < n; ++i)     
        {
            for(int j = 0; j <= (n - i - 1); ++j)  
            {   
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                } 
            }
        }
    }
     
    // Driver Code
    static public void Main ()
    {
        int n = 5;
        int[] arr = { 2, 0, 1, 4, 3 };
         
        Bubble_Sort(arr, n);
         
        Console.Write("The Sorted Array by using Bubble Sort is : ");
        for(int i = 0; i < n; ++i){
            Console.Write(arr[i]+" ");
        }
    }
}
 
// This code is contributed by Shubhamsingh10

<script>
// Javascript program for the above approach
 
function Bubble_Sort( arr, n) 
{
    for(var i = 1; i < n; ++i)     
    {   
        for(var j = 0; j <= (n - i - 1); ++j)  
        {   
            if(arr[j] > arr[j + 1]){
                var temm = arr[j];
                arr[j] = arr[j + 1];
                arr[j+1] = temm;
             }
        }
    }
}
 
 
var n = 5;
var arr = [2, 0, 1, 4, 3];
Bubble_Sort(arr, n);
document.write("The Sorted Array by using Bubble Sort is : ");
for(var i = 0; i < n; i++){
    document.write(arr[i]+" ");
}
 
// This code is contributed by Shubhamsingh10
</script>

The Sorted Array by using Bubble Sort is : 0 1 2 3 4 

Adición de inteligencia a la clasificación de burbujas:

1. Debemos tener en cuenta el hecho de que incluso si nuestros datos están ordenados inicialmente, nuestro algoritmo actual realizará todas las iteraciones.
2. Como se muestra en el código anterior, intercambiamos dos elementos (por ejemplo, i e i+1) cuando arr[i] > arr[i+1]. Por lo tanto, incluso si nuestros datos ya están ordenados (o se ordenan justo después de algunas iteraciones), nuestro algoritmo aún se ejecutará,
3. Sin embargo, podemos modificar nuestro código para que nuestro algoritmo reconozca cuándo se ordenan los datos proporcionados y no se requieren más iteraciones.
    
4. Podemos lograr esto simplemente agregando una variable de «bandera» . Inicialice esta variable de «bandera» en falso fuera del bucle interno y configúrela en verdadero si en cualquier punto (arr[j] > arr[j+1]) la condición es verdadera.
5. Después de salir del bucle interno, marque la bandera. Si flag == true , es decir, se cambió y se llevó a cabo la operación de intercambio. Sin embargo, si flag == false, significa que no se realizó ningún intercambio durante toda la iteración y, por lo tanto, nuestros datos ahora están ordenados y no se requieren más iteraciones.

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function for bubble sort
void Bubble_Sort(int arr[], int n)
{
    bool flag;
   
    // Iterate from 1 to n - 1
    for (int i = 1; i < n; ++i) {
 
        flag = false;
       
        // Iterate from 0 to n - i - 1
        for (int j = 0; j <= (n - i - 1); ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }
        if (flag == false)
            break;
    }
}
 
// Driver Code
int main()
{
    int n = 5;
    int arr[5] = { 2, 0, 1, 4, 3 };
    Bubble_Sort(arr, n);
    cout << "The Sorted Array by using Bubble Sort is : ";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function for bubble sort
static void Bubble_Sort(int[] arr, int n)
{
    boolean flag;
   
    // Iterate from 1 to n - 1
    for(int i = 1; i < n; ++i)
    {
        flag = false;
       
        // Iterate from 0 to n - i - 1
        for(int j = 0; j <= (n - i - 1); ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp  = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (flag == false)
            break;
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 5;
    int[] arr = { 2, 0, 1, 4, 3 };
    Bubble_Sort(arr, n);
    System.out.print("The Sorted Array by " +
                     "using Bubble Sort is : ");
     
    for(int i = 0; i < n; ++i)
        System.out.print(arr[i] + " ");
}
}
 
// This code is contributed by shubhamsingh10

# Python3 program for the above approach
 
# Function for bubble sort
def Bubble_Sort(arr, n):
    flag = True
     
    # Iterate from 1 to n - 1
    for i in range(1,n):
        flag = False
        # Iterate from 0 to n - i - 1
        for j in range(n-i):
            if (arr[j] > arr[j + 1]):
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
         
        if (flag == False):
            break
         
# Driver Code
n = 5
arr = [2, 0, 1, 4, 3]
Bubble_Sort(arr, n)
print("The Sorted Array by using Bubble Sort is : ", end='')
for i in range(n):
    print(arr[i], end= " ")
 
# This code is contributed by ShubhamSingh10

// C# program for the above approach
using System;
public class GFG{
     
    // Function for bubble sort
    static void Bubble_Sort(int[] arr, int n)
    {
        bool flag;
       
        // Iterate from 1 to n - 1
        for (int i = 1; i < n; ++i) {
     
            flag = false;
           
            // Iterate from 0 to n - i - 1
            for (int j = 0; j <= (n - i - 1); ++j) {
                if (arr[j] > arr[j + 1]) {
                    int temp  = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (flag == false)
                break;
        }
    }
     
    // Driver Code
    static public void Main ()
    {
        int n = 5;
        int[] arr = { 2, 0, 1, 4, 3 };
        Bubble_Sort(arr, n);
        Console.Write("The Sorted Array by using Bubble Sort is : ");
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
    }
 
}
 
// This code is contributed by shubhamsingh10.

<script>
 
// JavaScript program for the above approach
  
// Function for bubble sort
function Bubble_Sort(arr, n)
{
    Boolean(flag = true);
     
    // Iterate from 1 to n - 1
    for(var i = 1; i < n; ++i)
    {
        flag = false;
       
        // Iterate from 0 to n - i - 1
        for(var j = 0; j <= (n - i - 1); ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                var temp  = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (flag == false)
            break;
    }
}
 
// Driver Code
var n = 5;
var arr = [ 2, 0, 1, 4, 3 ];
Bubble_Sort(arr, n);
 
document.write("The Sorted Array by " +
                 "using Bubble Sort is : ");
 
for(var i = 0; i < n; ++i)
    document.write(arr[i] + " ");
 
// This code is contributed by shivanisinghss2110
 
</script>

The Sorted Array by using Bubble Sort is : 0 1 2 3 4 

NOTA: Este pequeño ajuste no cambia la complejidad de tiempo del peor de los casos del algoritmo de clasificación de burbujas, pero puede mejorar su tiempo de ejecución para casos particulares.

Veamos las diferencias entre Bubble Sort y Selection Sort en forma tabular:
 

Referencias:  
Lectura de conferencias
Implementar tipo de burbuja c