Comparación entre Bubble Sort, Selection Sort y Insertion Sort

1. Clasificación de burbujas

La ordenación de burbujas compara e intercambia repetidamente (si es necesario) elementos adyacentes en cada pasada. En la i-ésima pasada de Bubble Sort (orden ascendente), los últimos (i-1) elementos ya están ordenados , y el i-ésimo elemento más grande se coloca en la (Ni)-ésima posición, es decir, la i-ésima última posición. 

Algoritmo: 

BubbleSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 1 to (N-1) ) // N elements => (N-1) pass
    {
    // Swap adjacent elements of Arr[1:(N-I)]such that
    // largest among { Arr[1], Arr[2], ..., Arr[N-I] } reaches to Arr[N-I]
        For ( J:= 1 to  (N-I) ) // Execute the pass
        {
            If ( Arr [J] > Arr[J+1] ) 
                Swap( Arr[j], Arr[J+1] );
        }
    }
}

Optimización del algoritmo : compruebe si ocurrió alguna operación de intercambio en el bucle interno (bucle de ejecución de pase) o no. Si no hay intercambio en ningún paso, significa que la array ahora está completamente ordenada, por lo tanto, no es necesario continuar, detenga la operación de clasificación. Entonces podemos optimizar la cantidad de pases cuando la array se ordena antes de completar todos los pases. Y también puede detectar si la array dada / de entrada está ordenada o no, en el primer paso. 

BubbleSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 1 to (N-1) ) // N elements => (N-1) pass
    {
    // Swap adjacent elements of Arr[1:(N-I)]such that
    // largest among { Arr[1], Arr[2], ..., Arr[N-I] } reaches to Arr[N-I]
        noSwap = true; // Check occurrence of swapping in inner loop
        For ( J:= 1 to  (N-I) ) // Execute the pass
        {
            If ( Arr [J] > Arr[J+1] )
            { 
                Swap( Arr[j], Arr[J+1] );
                noSwap = false;
            }
        }
        If (noSwap) // exit the loop
            break;
    }
}

Complejidad del tiempo : 

• Array ordenada en el mejor de los casos como entrada. O casi todos los elementos están en el lugar adecuado. [ O(N) ]. O(1) intercambios.
• En el peor de los casos : ordenación inversa/muy pocos elementos están en el lugar adecuado. [ O(N ² ) ] . O(N ² ) intercambios.
• Caso Promedio : [ O(N ² ) ] . O(N ² ) intercambios.

Complejidad espacial : se utiliza una variable temporal en el intercambio [auxiliar, O(1) ]. Por lo tanto, es una ordenación in situ. 

Ventaja :  

1. Es el método de clasificación más simple.
2. La complejidad del mejor caso es de O (N) [para un enfoque optimizado] mientras se ordena la array.
3. Usando un enfoque optimizado , puede detectar una array ya ordenada en el primer paso con una complejidad de tiempo de O(N) .
4. Ordenación estable: no cambia el orden relativo de los elementos con claves iguales.
5. Clasificación en el lugar.

Desventaja :  

1. Bubble sort es un algoritmo comparativamente más lento.

2. Clasificación de selección

La ordenación por selección selecciona el i-ésimo elemento más pequeño y lo coloca en la i-ésima posición. Este algoritmo divide la array en dos partes: subarreglo ordenado (izquierda) y no ordenado (derecha). Selecciona el elemento más pequeño de un subarreglo no ordenado y lo coloca en la primera posición de ese subarreglo (orden ascendente). Selecciona repetidamente el siguiente elemento más pequeño. 

Algoritmo : 

SelectionSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 1 to (N-1) ) // N elements => (N-1) pass
    {
    // I=N is ignored, Arr[N] is already at proper place.
    // Arr[1:(I-1)] is sorted subarray, Arr[I:N] is undorted subarray
    // smallest among { Arr[I], Arr[I+1], Arr[I+2], ..., Arr[N] } is at place min_index
        
        min_index = I;
        For ( J:= I+1 to N ) // Search Unsorted Subarray (Right lalf)
        {
            If ( Arr [J] < Arr[min_index] ) 
                min_index = J; // Current minimum
        }
        // Swap I-th smallest element with current I-th place element
        If (min_Index != I)
              Swap ( Arr[I], Arr[min_index] ); 
        
    }
}

Complejidad del tiempo : 

• Mejor caso [ O(N ² ) ]. Y O(1) se intercambia.
• Peor caso : Ordenado a la inversa, y cuando el bucle interno hace una comparación máxima. [ O(N ² ) ] . También, intercambios O(N) .
• Caso Promedio : [ O(N ² ) ] . También intercambios O(N) .

Complejidad espacial : [auxiliar, O(1) ]. Clasificación en el lugar. (Cuando los elementos se desplazan en lugar de intercambiarse (es decir, temp=a[min], luego se desplazan los elementos de ar[i] a ar[min-1] un lugar hacia arriba y luego se coloca a[i]=temp ). Si se opta por el intercambio, el algoritmo no está en el lugar). 

Ventaja :  

1. También se puede usar en estructuras de lista que hacen que agregar y quitar sea eficiente, como una lista enlazada. Simplemente elimine el elemento más pequeño de la parte sin clasificar y termine al final de la parte clasificada.
2. Se redujo el número de swaps. O(N) swaps en todos los casos.
3. Clasificación en el lugar.

Desventaja : 

1. La complejidad del tiempo en todos los casos es O(N ² ) , sin el mejor de los casos.

3. Clasificación por inserción

La clasificación por inserción es un algoritmo de clasificación basado en una comparación simple. Inserta cada elemento de la array en su posición adecuada. En la i-ésima iteración, los elementos anteriores (i-1) (es decir, el subarreglo Arr[1:(i-1)]) ya están ordenados, y el i-ésimo elemento (Arr[i]) se inserta en su lugar adecuado en el subarreglo previamente ordenado. 
Encuentra más detalles en este GFG Link . 

Algoritmo : 

InsertionSort (Arr, N) // Arr is an array of size N.
{
    For ( I:= 2 to N ) // N elements => (N-1) pass
    {
    // Pass 1 is trivially sorted, hence not considered
    // Subarray { Arr[1], Arr[2], ..., Arr[I-I] } is already sorted
        
        insert_at = I; // Find suitable position insert_at, for Arr[I]
        // Move subarray Arr [ insert_at: I-1 ] to one position right

        item = Arr[I]; J=I-1;
        While ( J ? 1 && item < Arr[J] ) 
        {
                Arr[J+1] = Arr[J]; // Move to right   
                // insert_at = J;
                J--;
            }
            insert_at = J+1; // Insert at proper position
            Arr[insert_at] = item; // Arr[J+1] = item;
        }
    }
}

Complejidad del tiempo :  

• Array ordenada en el mejor de los casos como entrada, [ O(N) ]. Y O(1) se intercambia.
• En el peor de los casos : ordenación inversa, y cuando el bucle interno realiza la comparación máxima, [ O(N ² ) ] . Y O(N ² ) se intercambia.
• Caso Promedio : [ O(N ² ) ] . Y O(N ² ) se intercambia.

Complejidad espacial : [auxiliar, O(1) ]. Clasificación en el lugar. 

Ventaja :  

1. Se puede calcular fácilmente.
2. La complejidad del mejor de los casos es de O (N) mientras que la array ya está ordenada.
3. Número de intercambios reducido que el tipo de burbuja.
4. Para valores más pequeños de N, la ordenación por inserción funciona de manera eficiente como otros algoritmos de ordenación cuadrática.
5. Ordenación estable.
6. Adaptativo: el número total de pasos se reduce para una array ordenada parcialmente.
7. Clasificación en el lugar.

Desventaja :  

1. Generalmente se usa cuando el valor de N es pequeño. Para valores más grandes de N , es ineficiente . 
    

Complejidad de tiempo y espacio:  

Algoritmo de clasificación	Complejidad del tiempo			Complejidad espacial
	Mejor caso	Caso promedio	Peor de los casos	Peor de los casos
Ordenamiento de burbuja	EN)	O(N 2 )	O(N 2 )	O(1)
Clasificación de selección	O(N 2 )	O(N 2 )	O(N 2 )	O(1)
Tipo de inserción	EN)	O(N 2 )	O(N 2 )	O(1)