#!/bin/sh -
# selectionsort
# Selection sort using an array
function selection_sort {
size=${#A[*]}
for (( i=0; i < size-1; i++ )); do
lowest=$i
for (( j=i+1; j < size; j++ )); do
[ ${A[j]} -lt ${A[lowest]} ] && lowest=$j
done
[ $lowest -eq $i ] && continue
temp=${A[i]}; A[i]=${A[lowest]}; A[lowest]=$temp
done
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
selection_sort
echo $'Result:\n'${A[*]}
exit 0
#!/bin/sh -
# bubblesort
# Bubble sort using an array
function bubble_sort {
size=${#A[*]}
for (( j=1; j < size; j++ )); do
for (( i=0; i < size-j; i++ )); do
if [ ${A[i+1]} -lt ${A[i]} ]; then
temp=${A[i]}; A[i]=${A[i+1]}; A[i+1]=$temp
fi
done
done
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
bubble_sort
echo $'Result:\n'${A[*]}
exit 0
#!/bin/sh -
# insertionsort
# Insertion sort using an array
function insertion_sort {
size=${#A[*]}
for (( i=1; i<size; i++ )); do
v=${A[i]}; j=$i
while [ $j -gt 0 ] && [ ${A[j-1]} -gt $v ]; do
A[j]=${A[j-1]}
(( j-=1 ))
done
A[j]=$v
done
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
insertion_sort
echo $'Result:\n'${A[*]}
exit 0
#!/bin/sh -
# shellsort
# Shell sort using an array
function shell_sort {
size=${#A[*]}
h=1; until [ $h -gt $size ]; do h=$((3*h+1)); done
until [ $h -eq 1 ]; do
(( h/=3 ))
for (( i=h; i < size; i++ )); do
v=${A[i]}; j=$i
while [ $j -ge $h ] && [ ${A[j-h]} -gt $v ]; do
A[j]=${A[j-h]};
(( j-=h ))
[ $j -le $h ] && break
done
[ $i -eq $j ] || A[j]=$v
done
done
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
shell_sort
echo $'Result:\n'${A[*]}
exit 0
#!/bin/sh -
# countingsort
# Counting sort using 3 arrays
function counting_sort {
size=${#A[*]}
k=${A[0]}
declare -a B
C[0]=0
for (( j=0; j<size; j++ ));do
[ ${A[j]} -gt $k ] && k=${A[j]}
(( C[${A[j]}] += 1 ))
done
for (( i=1; i<=k; i++ ));do
(( C[i] += ${C[i-1]} ))
done
for (( j=size-1; j>=0; j-- ));do
B[${C[${A[j]}]}]=${A[j]}
(( C[${A[j]}]-=1 ))
done
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
counting_sort
echo $'Result:\n'${B[*]}
exit 0
#!/bin/sh -
# quicksort
# Quick Sort using an array
function partition {
local p r
p=$1; r=$2
x=${A[r]}
i=$((p-1))
for (( j=p; j < r; j++ )); do
if [ ${A[j]} -le $x ]; then
((i+=1))
temp=${A[i]}; A[i]=${A[j]}; A[j]=$temp
fi
done
temp=${A[i+1]}; A[i+1]=${A[r]}; A[r]=$temp
return
}
function quick_sort {
local p r
p=$1; r=$2
[ $p -ge $r ] && return
partition $p $r
q=$((i+1))
quick_sort $p $((q-1))
quick_sort $((q+1)) $r
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
size=${#A[*]}
quick_sort 0 $(($size-1))
echo $'Result:\n'${A[*]}
exit 0
#!/bin/sh -
# mergesort
# Merge sort using an array
function merge {
local i j k p q r
p=$1; q=$2; r=$3
n1=$((q-p+1))
n2=$((r-q))
for (( i=1; i <= n1; i++ )); do
L[i-1]=${A[p+i-2]}
done
for (( j=1; j <= n2; j++ )); do
R[j-1]=${A[q+j-1]}
done
L[n1]=$((2**31-1))
R[n2]=$((2**31-1))
i=1; j=1
for (( k=p; k <= r; k++ )); do
if [ ${L[i-1]} -le ${R[j-1]} ]; then
A[k-1]=${L[i-1]}
((i+=1))
else
A[k-1]=${R[j-1]}
((j+=1))
fi
done
return
}
function merge_sort {
local p q r
p=$1; r=$2
if [ $p -lt $r ]; then
q=$(( (p+r)/2 ))
merge_sort $p $q
merge_sort $((q+1)) $r
merge $p $q $r
fi
return
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
size=${A[*]}
merge_sort 1 $size
echo $'Result:\n'${A[*]}
exit 0
#!/bin/sh -
# heapsort
# Heap sort using an array
function maxheapify {
local i
i=$1
l=$((2*i))
r=$((2*i+1))
if [ $l -le $heapsize ] && [ ${A[l-1]} -gt ${A[i-1]} ]; then
largest=$l
else
largest=$i
fi
if [ $r -le $heapsize ] && [ ${A[r-1]} -gt ${A[largest-1]} ]; then
largest=$r
fi
if [ $largest -ne $i ]; then
temp=${A[i-1]}; A[i-1]=${A[largest-1]}; A[largest-1]=$temp
maxheapify $largest
fi
return 0
}
function buildmaxheap {
local i
heapsize=${#A[*]}
for (( i=${#A[*]}/2; i >= 1; i-- )); do
maxheapify $i
done
}
function heap_sort {
local i
buildmaxheap
for (( i=${#A[*]}; i >= 2; i-- ));do
temp=${A[i-1]}; A[i-1]=${A[1-1]}; A[1-1]=$temp
(( heapsize-=1 ))
maxheapify 1
done
}
A=(39 5 36 12 9 3 2 30 4 18 22 28 25 1)
heap_sort
echo $'Result:\n'${A[*]}
exit 0
|
This site best viewed with a browser |
| Warning: This is a Debian centric site | |
| Many thanks to Debra and Ian Murdock for making Debian possible | |
| First created Apr 22, 2008 ~ Last revised December 25, 2009 |
