| 1 | package Algorithm::Sorting; | ||
| 2 | |||
| 3 | use warnings; | ||
| 4 | use strict; | ||
| 5 | |||
| 6 | our $VERSION = '0.05'; | ||
| 7 | |||
| 8 | |||
| 9 | BEGIN { | ||
| 10 | use Exporter(); | ||
| 11 | our @ISA=qw(Exporter); | ||
| 12 | our @EXPORT=qw(&BubbleSort &ShakerSort &SelectionSort &InsertionSort &ShellSort &QuickSort); | ||
| 13 | } | ||
| 14 | |||
| 15 | |||
| 16 | sub _filter { | ||
| 17 | my $array=shift; | ||
| 18 | |||
| 19 | my @charstrings=grep(/[a-zA-Z]/, @$array); | ||
| 20 | my @numbers=grep(/^-?\d*\.?\d*$/, @$array); | ||
| 21 | |||
| 22 | return \@charstrings, $#charstrings+1, \@numbers, $#numbers+1; | ||
| 23 | } | ||
| 24 | |||
| 25 | |||
| 26 | sub BubbleSort { | ||
| 27 | my $referenceOfItemList=shift; | ||
| 28 | my ($c, $cc, $n, $nc)=_filter($referenceOfItemList); | ||
| 29 | |||
| 30 | my ($a, $b, $t); | ||
| 31 | for($a=1; $a<$cc; ++$a) { | ||
| 32 | for($b=$cc-1; $b>=$a; --$b) { | ||
| 33 | if($c->[$b-1] gt $c->[$b]) { | ||
| 34 | $t=$c->[$b-1]; | ||
| 35 | $c->[$b-1]=$c->[$b]; | ||
| 36 | $c->[$b]=$t; | ||
| 37 | } | ||
| 38 | } | ||
| 39 | } | ||
| 40 | |||
| 41 | $a=undef; $b=undef, $t=undef; | ||
| 42 | for($a=1; $a<$nc; ++$a) { | ||
| 43 | for($b=$nc-1; $b>=$a; --$b) { | ||
| 44 | if($n->[$b-1] > $n->[$b]) { | ||
| 45 | $t=$n->[$b-1]; | ||
| 46 | $n->[$b-1]=$n->[$b]; | ||
| 47 | $n->[$b]=$t; | ||
| 48 | } | ||
| 49 | } | ||
| 50 | } | ||
| 51 | |||
| 52 | @$referenceOfItemList=(@$n, @$c); | ||
| 53 | } | ||
| 54 | |||
| 55 | |||
| 56 | sub ShakerSort { | ||
| 57 | my $referenceOfItemList=shift; | ||
| 58 | my ($c, $cc, $n, $nc)=_filter($referenceOfItemList); | ||
| 59 | |||
| 60 | my ($a, $exchange, $t); | ||
| 61 | do { | ||
| 62 | $exchange=0; | ||
| 63 | for($a=$cc-1; $a>0; --$a) { | ||
| 64 | if($c->[$a-1] gt $c->[$a]) { | ||
| 65 | $t=$c->[$a-1]; | ||
| 66 | $c->[$a-1]=$c->[$a]; | ||
| 67 | $c->[$a]=$t; | ||
| 68 | $exchange=1; | ||
| 69 | } | ||
| 70 | } | ||
| 71 | |||
| 72 | for($a=1; $a<$cc; ++$a) { | ||
| 73 | if($c->[$a-1] gt $c->[$a]) { | ||
| 74 | $t=$c->[$a-1]; | ||
| 75 | $c->[$a-1]=$c->[$a]; | ||
| 76 | $c->[$a]=$t; | ||
| 77 | $exchange=1; | ||
| 78 | } | ||
| 79 | } | ||
| 80 | } while($exchange); | ||
| 81 | |||
| 82 | $a=undef; $exchange=undef; $t=undef; | ||
| 83 | do { | ||
| 84 | $exchange=0; | ||
| 85 | for($a=$nc-1; $a>0; --$a) { | ||
| 86 | if($n->[$a-1] > $n->[$a]) { | ||
| 87 | $t=$n->[$a-1]; | ||
| 88 | $n->[$a-1]=$n->[$a]; | ||
| 89 | $n->[$a]=$t; | ||
| 90 | $exchange=1; | ||
| 91 | } | ||
| 92 | } | ||
| 93 | |||
| 94 | for($a=1; $a<$nc; ++$a) { | ||
| 95 | if($n->[$a-1] > $n->[$a]) { | ||
| 96 | $t=$n->[$a-1]; | ||
| 97 | $n->[$a-1]=$n->[$a]; | ||
| 98 | $n->[$a]=$t; | ||
| 99 | $exchange=1; | ||
| 100 | } | ||
| 101 | } | ||
| 102 | } while($exchange); | ||
| 103 | |||
| 104 | @$referenceOfItemList=(@$n, @$c); | ||
| 105 | } | ||
| 106 | |||
| 107 | sub SelectionSort { | ||
| 108 | my $referenceOfItemList=shift; | ||
| 109 | my ($c, $cc, $n, $nc)=_filter($referenceOfItemList); | ||
| 110 | |||
| 111 | my ($a, $b, $d, $t, $exchange); | ||
| 112 | |||
| 113 | for($a=0; $a<$cc-1; ++$a) { | ||
| 114 | $exchange=0; | ||
| 115 | $d=$a; | ||
| 116 | $t=$c->[$a]; | ||
| 117 | |||
| 118 | for($b=$a+1; $b < $cc; ++$b) { | ||
| 119 | if($c->[$b] lt $t) { | ||
| 120 | $d=$b; | ||
| 121 | $t=$c->[$b]; | ||
| 122 | $exchange=1; | ||
| 123 | } | ||
| 124 | } | ||
| 125 | if($exchange) { | ||
| 126 | $c->[$d]=$c->[$a]; | ||
| 127 | $c->[$a]=$t; | ||
| 128 | } | ||
| 129 | } | ||
| 130 | |||
| 131 | $a=undef; $b=undef; $d=undef; $exchange=undef; | ||
| 132 | for($a=0; $a<$nc-1; ++$a) { | ||
| 133 | $exchange=0; | ||
| 134 | $d=$a; | ||
| 135 | $t=$n->[$a]; | ||
| 136 | |||
| 137 | for($b=$a+1; $b < $nc; ++$b) { | ||
| 138 | if($n->[$b] < $t) { | ||
| 139 | $d=$b; | ||
| 140 | $t=$n->[$b]; | ||
| 141 | $exchange=1; | ||
| 142 | } | ||
| 143 | } | ||
| 144 | if($exchange) { | ||
| 145 | $n->[$d]=$n->[$a]; | ||
| 146 | $n->[$a]=$t; | ||
| 147 | } | ||
| 148 | } | ||
| 149 | |||
| 150 | @$referenceOfItemList=(@$n, @$c); | ||
| 151 | } | ||
| 152 | |||
| 153 | sub InsertionSort { | ||
| 154 | my $referenceOfItemList=shift; | ||
| 155 | my ($c, $cc, $n, $nc)=_filter($referenceOfItemList); | ||
| 156 | |||
| 157 | my ($a, $b, $t); | ||
| 158 | |||
| 159 | for($a=1; $a<$cc; ++$a) { | ||
| 160 | $t=$c->[$a]; | ||
| 161 | for($b=$a-1; ($b>=0) && ($t lt $c->[$b]); $b--) { | ||
| 162 | $c->[$b+1]=$c->[$b]; | ||
| 163 | } | ||
| 164 | $c->[$b+1]=$t; | ||
| 165 | } | ||
| 166 | |||
| 167 | $a=undef; $b=undef; $t=undef; | ||
| 168 | for($a=1; $a<$nc; ++$a) { | ||
| 169 | $t=$n->[$a]; | ||
| 170 | for($b=$a-1; ($b>=0) && ($t < $n->[$b]); $b--) { | ||
| 171 | $n->[$b+1]=$n->[$b]; | ||
| 172 | } | ||
| 173 | $n->[$b+1]=$t; | ||
| 174 | } | ||
| 175 | |||
| 176 | @$referenceOfItemList=(@$n, @$c); | ||
| 177 | } | ||
| 178 | |||
| 179 | sub ShellSort { | ||
| 180 | my $referenceOfItemList=shift; | ||
| 181 | my ($c, $cc, $n, $nc)=_filter($referenceOfItemList); | ||
| 182 | |||
| 183 | my ($i, $j, $gap, $k, $x); | ||
| 184 | |||
| 185 | my @a=(9, 5, 3, 2, 1); | ||
| 186 | |||
| 187 | for($k=0; $k<5; $k++) { | ||
| 188 | $gap=$a[$k]; | ||
| 189 | for($i=$gap; $i<$cc; ++$i) { | ||
| 190 | $x=$c->[$i]; | ||
| 191 | for($j=$i-$gap; ($x lt $c->[$j]) && ($j>=0); $j=$j-$gap) { | ||
| 192 | $c->[$j+$gap]=$c->[$j]; | ||
| 193 | } | ||
| 194 | $c->[$j+$gap]=$x; | ||
| 195 | } | ||
| 196 | } | ||
| 197 | |||
| 198 | $i=undef; $j=undef; $gap=undef; $k=undef; $x=undef; | ||
| 199 | for($k=0; $k<5; $k++) { | ||
| 200 | $gap=$a[$k]; | ||
| 201 | for($i=$gap; $i<$nc; ++$i) { | ||
| 202 | $x=$n->[$i]; | ||
| 203 | for($j=$i-$gap; ($x < $n->[$j]) && ($j>=0); $j=$j-$gap) { | ||
| 204 | $n->[$j+$gap]=$n->[$j]; | ||
| 205 | } | ||
| 206 | $n->[$j+$gap]=$x; | ||
| 207 | } | ||
| 208 | } | ||
| 209 | |||
| 210 | @$referenceOfItemList=(@$n, @$c); | ||
| 211 | } | ||
| 212 | |||
| 213 | sub QuickSort { | ||
| 214 | my $referenceOfItemList=shift; | ||
| 215 | my ($c, $cc, $n, $nc)=_filter($referenceOfItemList); | ||
| 216 | |||
| 217 | _quicksortNumber($n, 0, $nc-1); | ||
| 218 | _quicksortChar($c, 0, $cc-1); | ||
| 219 | |||
| 220 | @$referenceOfItemList=(@$n, @$c); | ||
| 221 | } | ||
| 222 | |||
| 223 | sub _quicksortChar { | ||
| 224 | my ($list, $left, $right)=@_; | ||
| 225 | |||
| 226 | my ($i, $j, $x, $y); | ||
| 227 | |||
| 228 | $i=$left; | ||
| 229 | $j=$right; | ||
| 230 | |||
| 231 | $x=$list->[($left + $right)/2]; | ||
| 232 | |||
| 233 | do { | ||
| 234 | $i++ while($list->[$i] && ($list->[$i] lt $x) && ($i<$right)); | ||
| 235 | $j-- while($x && ($x lt $list->[$j]) && ($j>$left)); | ||
| 236 | |||
| 237 | if($i <= $j) { | ||
| 238 | $y=$list->[$i]; | ||
| 239 | $list->[$i]=$list->[$j]; | ||
| 240 | $list->[$j]=$y; | ||
| 241 | $i++; | ||
| 242 | $j--; | ||
| 243 | } | ||
| 244 | } while($i <= $j); | ||
| 245 | |||
| 246 | _quicksortChar($list, $left, $j) if($left < $j); | ||
| 247 | _quicksortChar($list, $i, $right) if($j < $right); | ||
| 248 | } | ||
| 249 | |||
| 250 | sub _quicksortNumber { | ||
| 251 | my ($list, $left, $right)=@_; | ||
| 252 | |||
| 253 | my ($i, $j, $x, $y); | ||
| 254 | |||
| 255 | $i=$left; | ||
| 256 | $j=$right; | ||
| 257 | |||
| 258 | $x=$list->[($left + $right)/2]; | ||
| 259 | |||
| 260 | do { | ||
| 261 | $i++ while($list->[$i] && ($list->[$i] < $x) && ($i<$right)); | ||
| 262 | $j-- while(( $x < $list->[$j]) && ($j>$left)); | ||
| 263 | |||
| 264 | if($i <= $j) { | ||
| 265 | $y=$list->[$i]; | ||
| 266 | $list->[$i]=$list->[$j]; | ||
| 267 | $list->[$j]=$y; | ||
| 268 | $i++; | ||
| 269 | $j--; | ||
| 270 | } | ||
| 271 | } while($i <= $j); | ||
| 272 | |||
| 273 | _quicksortNumber($list, $left, $j) if($left < $j); | ||
| 274 | _quicksortNumber($list, $i, $right) if($j < $right); | ||
| 275 | } | ||
| 276 | |||
| 277 | |||
| 278 | return 1; | ||
| 279 | |||
| 280 | END {} | ||
| 281 | |||
| 282 | |||
| 283 | __END__ |