1 #!/bin/bash 2 3 4 if [ $COMMENT_BLOCK ]; then 5 Bash Shell script implementation 6 of Heapsort. 7 GNU bash, version 2.05b. 8 Author: John Bryan, Jr. 9 Date: September 10, 2006 10 Opens file, integers.txt, containing 11 variable number of integers. 12 Output is to screen. Redirection operator 13 can be used on command line to output to file. 14 15 fi 16 17 18 GetIntegers () 19 { 20 INTFILE=$(find . -name "integers.txt") 21 exec 6<$INTFILE 22 while read -u 6 dta 23 do 24 echo "$dta" 25 done 26 exec 6<&- 27 } 28 29 30 Swap () 31 { 32 p2S_a=( `echo $1` ) 33 p2S_i_i=( `echo $2` ) 34 p2S_j_i=( `echo $3` ) 35 temp_i="${p2S_a[$p2S_i_i]}" 36 p2S_a[$p2S_i_i]="${p2S_a[$p2S_j_i]}" 37 p2S_a[$p2S_j_i]="$temp_i" 38 echo "${p2S_a[@]}" 39 } 40 41 42 ConstructHeap() 43 { 44 p2CH_a=$1 45 p2CH_N_i=$2 46 printf "\n" 47 let X=$p2CH_N_i-1; 48 printf "\n" 49 while [ "$X" -ge 0 ] 50 do 51 let X=X-1 52 arg21=`echo ${p2CH_a[@]}` 53 arg22=`echo $X+1` 54 arg23=`echo "$p2CH_N_i"` 55 p2CH_a=( `Bubbledown "$arg21" "$arg22" "$arg23"` ) 56 done 57 echo "${p2CH_a[@]}" 58 } 59 60 61 Bubbledown() 62 { 63 declare -i i 64 declare -i j 65 declare -i k 66 declare -i w 67 declare -i x 68 declare -i y 69 declare -i c1 70 declare -i u 71 declare -i N2 72 P2BD_a=( `echo $1` ) 73 X=( `echo $2` ) 74 N2=( `echo $3` ) 75 j=$2 76 while [ 0 -eq 0 ] 77 do 78 k="$j" 79 u=0 80 x=0 81 let w=2*k+1 82 if [ "$w" -lt "$N2" ] 83 then 84 x="${P2BD_a["$w"]}" 85 fi 86 y="${P2BD_a["$j"]}" 87 let c1=2*k+2 88 if [ "$c1" -lt "$N2" ] 89 then 90 u="${P2BD_a["$c1"]}" 91 fi 92 if [ "$w" -lt "$N2" ] 93 then 94 if [ "$x" -gt "$y" ] 95 then 96 let j=2*k+1 97 fi 98 fi 99 y="${P2BD_a["$j"]}" 100 if [ "$c1" -lt "$N2" ] 101 then 102 if [ "$u" -gt "$y" ] 103 then 104 let j=2*k+2 105 fi 106 fi 107 BD2S_arg1_a=`echo ${P2BD_a[@]}` 108 BD2S_arg2_i=`echo $k` 109 BD2S_arg3_i=`echo $j` 110 P2BD_a=( `Swap "$BD2S_arg1_a" "$BD2S_arg2_i" "$BD2S_arg3_i"` ) 111 if [ "$BD2S_arg2_i" -eq "$BD2S_arg3_i" ] 112 then 113 break 114 fi 115 done 116 echo "${P2BD_a[@]}" 117 } 118 119 120 Heapsort() 121 { 122 p2HS_a=( `echo "$1"` ) 123 p2HS_N_i=( `echo "$2"` ) 124 let count=$p2HS_N_i-1 125 while [ "$count" -gt 0 ] 126 do 127 let index=count 128 let count=count-1 129 rr1=`echo ${p2HS_a[@]}` 130 rr2=`echo $index` 131 rr3=0 132 p2HS_a=( `Swap "$rr1" "$rr2" "$rr3"` ) 133 br1=`echo ${p2HS_a[@]}` 134 br2=0 135 br3=`echo $index` 136 p2HS_a=( `Bubbledown "$br1" "$br2" "$br3"` ) 137 done 138 echo "${p2HS_a[@]}" 139 } 140 141 142 PrintArray() 143 { 144 declare -i number_of_elements 145 array_to_print=( `echo "$1"` ) 146 printf "\n" 147 count=0 148 while [ $count -lt $2 ] 149 do 150 printf "SortedArray[%d] = %d \n" $count ${array_to_print[$count]} 151 let count=count+1 152 done 153 return 0; 154 } 155 156 157 Algorithm() 158 { 159 IntArray=( `GetIntegers` ) 160 argument=`echo ${IntArray[@]}` 161 N=`echo ${#IntArray[@]}` 162 HeapArray=( `ConstructHeap "$argument" "$N"` ) 163 aa1=`echo ${HeapArray[@]}` 164 M=`echo ${#HeapArray[@]}` 165 sorted_array=( `Heapsort "$aa1" "$M"` ) 166 aa1=`echo ${sorted_array[@]}` 167 PrintArray "$aa1" "$M" 168 } 169 170 171 Algorithm 172 exit 0