Ordenar una array en Bash usando Bubble sort

Prerrequisito: Clasificación de burbuja 

Dada una array arr, ordene la array en orden ascendente utilizando secuencias de comandos bash.

Ejemplos:  

Input : 9 7 2 5
Output :
Array in sorted order :
2 5 7 9

Acercarse :

Para ordenar, la ordenación de burbuja de array es la técnica más simple. La ordenación de burbujas funciona intercambiando los elementos adyacentes si están en el orden incorrecto. 

Ejemplo: 

Given array - (9, 7, 2, 5)
After first iteration - (7, 2, 5, 9)
After second iteration - (2, 5, 7, 9)
and so on...

De esta manera, la array se ordena colocando el elemento mayor al final de la array.  

# Sorting the array in Bash 
# using Bubble sort

# Static input of Array
arr=(10 8 20 100 12)

echo "Array in original order"
echo ${arr[*]}

# Performing Bubble sort 
for ((i = 0; i<5; i++))
do
    
    for((j = 0; j<5-i-1; j++))
    do
    
        if [ ${arr[j]} -gt ${arr[$((j+1))]} ]
        then
            # swap
            temp=${arr[j]}
            arr[$j]=${arr[$((j+1))]}  
            arr[$((j+1))]=$temp
        fi
    done
done

echo "Array in sorted order :"
echo ${arr[*]}

Producción : 

Array in sorted order :
8 10 12 20 100

Implementación optimizada:  la función anterior siempre se ejecuta O (n ^ 2) incluso si la array está ordenada. Se puede optimizar deteniendo el algoritmo si el bucle interno no provocó ningún intercambio. 

n=5
arr=(10 8 20 100 12) 

echo "Original array is: ${arr[*]}";

flag=1;
for (( i = 0; i < $n-1; i++ ))
do
    flag=0;
    for ((j = 0; j < $n-1-$i; j++ ))
    do
        if [[ ${arr[$j]} -gt ${arr[$j+1]} ]]
        then
            temp=${arr[$j]};
            arr[$j]=${arr[$j+1]};
            arr[$j+1]=$temp;
            flag=1;
        fi
    done

    if [[ $flag -eq 0 ]]; then
          break;
    fi

Producción:

Original array is: 10 8 20 100 12
Final sorted Array is 8 10 12 20 100

Complejidad de tiempo de peor caso y promedio: O(n*n). El peor de los casos ocurre cuando una array se ordena de forma inversa.

Complejidad temporal del mejor caso : O(n). El mejor de los casos ocurre cuando la array ya está ordenada.

Espacio Auxiliar: O(1)

Casos límite: la ordenación de burbujas toma un tiempo mínimo (Orden de n) cuando los elementos ya están ordenados.

Clasificación en el lugar: Sí

Estable: Sí