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í
Publicación traducida automáticamente
Artículo escrito por Manish_100 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA