1
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