sorting algo stat

run.sh

#!/bin/sh

echo "started test"

# args
N_RUN=$1
echo $N_RUN
START_SIZE=$2
echo $START_SIZE
END_SIZE=$3
echo $END_SIZE
STEP=$4
echo $STEP
SORT=$5
echo $SORT

if [[ $5 = "./sortA" ]];
then
	FILE=sortA.csv
else
	FILE=sortB.csv
fi

let _time=0

run_gen()
{
	./gen $1 $2 > nums
}

gen_near_sorted()
{
	run_gen $1 "A"
	for ((i=0; i<5; i++))
	do
		low=$(shuf -i 0-$1 -n 1)
		high=$(shuf -i $low-$1+1 -n 1)
		printf "Swap %d and %d\n" "$low" "$high"
		cmd="${low}m${high} ${high}-m${low}- w q"
		{
		       printf "%dm%d\n" "$low" "$high"
		       printf "%d-m%d-\n" "$high" "$low"
		       printf "%s\n" w q
	       } | ed -s nums
	done
}

gen_dup_key()
{
	chars=abcdefghijklmnopqrstuvwxyz
	for i in {1..$1}
	do
		key=$(shuf -i 0-$(($1/4)) -n 1)
		#printf "%d " $key
		printf "%d " "$key" >> nums

		for i in {1..3}
		do
			printf "%c" "${chars:RANDOM%${#chars}:1}" >> nums
			#printf "%c" "${chars:RANDOM%${#chars}:1}"
		done
		echo >> nums
		#echo "end"
	done
}

test_stable()
{
	gen_dup_key $1
	$SORT < nums > out1
	sort -ns < nums > out2
	if [[ -z $(cmp --silent out1 out2) ]]
	then
		echo "is stable"
		printf "yes" >> $FILE
	else
		echo "is not stable"
		printf "no" >> $FILE
	fi
	rm -rf nums out1 out2
}

test_adaptive()
{
	printf "testing for adaptivity %d\n" "$1"
	for ((i=0;i<$N_RUN;i++))
	do
		gen_near_sorted $1
		t=$(/usr/bin/time -f %U $SORT < nums 2>&1 1> /dev/null)
		total="${total}+${t}"
		rm -rf nums
	done
	_time="$(echo "($total)/$N_RUN" | bc -l)"
}

test_sorted()
{
	printf "testing for sorted %d\n" "$1"
	let total=0
	for ((i=0; i<$N_RUN; i++))
	do
		run_gen $1 "A"
		t=$(/usr/bin/time -f %U $SORT < nums 2>&1 1> /dev/null)
		total="${total}+${t}"
		rm -rf nums
	done
	_time="$(echo "($total)/$N_RUN" | bc -l)"
}

test_reverse()
{
	printf "testing for reverse %d\n" "$1"
	let total=0
	for ((i=0; i<$N_RUN; i++))
	do
		run_gen $1 "D"
		t=$(/usr/bin/time -f %U $SORT < nums 2>&1 1> /dev/null)
		total="${total}+${t}"
		rm -rf nums
	done
	_time="$(echo "($total)/$N_RUN" | bc -l)"
}

test_random()
{
	printf "testing for random %d\n" "$1"
	let total=0
	for ((i=0; i<$N_RUN; i++))
	do
		run_gen $1 "R"
		t=$(/usr/bin/time -f %U $SORT < nums 2>&1 1> /dev/null)
		total="${total}+${t}"
		rm -rf nums
	done
	_time="$(echo "($total)/$N_RUN" | bc -l)"
}

print_time()
{
	printf "%.4f" "$_time" >> $FILE
}

printf "Size, Sorted, Reverse, Random, Nearly sorted, Stable?\n" > $FILE
for ((size=$START_SIZE; size<=$END_SIZE; size=size+$STEP))
do
	printf "\n$size, " >> $FILE
	test_sorted $size
	print_time
	printf ", " >> $FILE
	test_reverse $size
	print_time
	printf ", " >> $FILE
	test_random $size
	print_time
	printf ", " >> $FILE
	test_adaptive $size
	print_time
	printf ", " >> $FILE
	test_stable $size
done