1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
|
#!/bin/bash
# bubble.sh: Bubble sort, of sorts.
# Recall the algorithm for a bubble sort. In this particular version...
# With each successive pass through the array to be sorted,
#+ compare two adjacent elements, and swap them if out of order.
# At the end of the first pass, the "heaviest" element has sunk to bottom.
# At the end of the second pass, the next "heaviest" one has sunk next to bottom.
# And so forth.
# This means that each successive pass needs to traverse less of the array.
# You will therefore notice a speeding up in the printing of the later passes.
exchange()
{
# Swaps two members of the array.
local temp=${Countries[$1]} # Temporary storage
#+ for element getting swapped out.
Countries[$1]=${Countries[$2]}
Countries[$2]=$temp
return
}
declare -a Countries # Declare array,
#+ optional here since it's initialized below.
# Is it permissable to split an array variable over multiple lines
#+ using an escape (\)?
# Yes.
Countries=(Netherlands Ukraine Zaire Turkey Russia Yemen Syria \
Brazil Argentina Nicaragua Japan Mexico Venezuela Greece England \
Israel Peru Canada Oman Denmark Wales France Kenya \
Xanadu Qatar Liechtenstein Hungary)
# "Xanadu" is the mythical place where, according to Coleridge,
#+ Kubla Khan did a pleasure dome decree.
clear # Clear the screen to start with.
echo "0: ${Countries[*]}" # List entire array at pass 0.
number_of_elements=${#Countries[@]}
let "comparisons = $number_of_elements - 1"
count=1 # Pass number.
while [ "$comparisons" -gt 0 ] # Beginning of outer loop
do
index=0 # Reset index to start of array after each pass.
while [ "$index" -lt "$comparisons" ] # Beginning of inner loop
do
if [ ${Countries[$index]} \> ${Countries[`expr $index + 1`]} ]
# If out of order...
# Recalling that \> is ASCII comparison operator
#+ within single brackets.
# if [[ ${Countries[$index]} > ${Countries[`expr $index + 1`]} ]]
#+ also works.
then
exchange $index `expr $index + 1` # Swap.
fi
let "index += 1" # Or, index+=1 on Bash, ver. 3.1 or newer.
done # End of inner loop
# ----------------------------------------------------------------------
# Paulo Marcel Coelho Aragao suggests for-loops as a simpler altenative.
#
# for (( last = $number_of_elements - 1 ; last > 0 ; last-- ))
## Fix by C.Y. Hunt ^ (Thanks!)
# do
# for (( i = 0 ; i < last ; i++ ))
# do
# [[ "${Countries[$i]}" > "${Countries[$((i+1))]}" ]] \
# && exchange $i $((i+1))
# done
# done
# ----------------------------------------------------------------------
let "comparisons -= 1" # Since "heaviest" element bubbles to bottom,
#+ we need do one less comparison each pass.
echo
echo "$count: ${Countries[@]}" # Print resultant array at end of each pass.
echo
let "count += 1" # Increment pass count.
done # End of outer loop
# All done.
exit 0
|