#!/bin/bash

ARR=()

function read_array()
{
	for i in $(seq 1 $#)
	do
		ARR[$i]=$1
		shift
	done
}

function print_array()
{
	interval=$1
	shift
	__k=$1
	shift
	__l=$1
	shift
	echo -en '\r'
	for __i in $(seq 1 $1)
	do
		if [ "$__i" -eq "$__k" ]
		then
			echo -en '\033[1;33m'
		fi
		if [ "$__i" -eq "$__l" ]
		then
			echo -en '\033[1;31m'
		fi
		echo -n "${ARR[$__i]} "
		if [ "$__i" -eq "$__k" -o "$__i" -eq "$__l" ]
		then
			echo -en '\033[0m'
		fi
	done
	sleep $interval
}

function swap()
{
	TMP=${ARR[$1]}
	ARR[$1]=${ARR[$2]}
	ARR[$2]=$TMP
}

function bubble_sort()
{
	for i in $(seq 1 $#)
	do
		for j in $(seq $# -1 $(($i + 1)))
		do
			print_array 1 $(($j - 1)) $j $#
			if [ "${ARR[$(($j - 1))]}" -gt "${ARR[$j]}" ]
			then
				swap $((j - 1)) $j
				print_array 1 $j $(($j - 1)) $#
			fi
		done
	done
}

function insertion_sort()
{
	for i in $(seq 2 $#)
	do
		for j in $(seq $i -1 2)
		do
			print_array 1 $(($j - 1)) $j $#
			if [ "${ARR[$(($j - 1))]}" -le "${ARR[$j]}" ]
			then
				break
			fi
			swap $j $(($j - 1))
			print_array 1 $j $(($j - 1)) $#
		done
	done
}

function selection_sort()
{
	for p in $(seq 1 $#)
	do
		m=$p
		for i in $(seq $(($p + 1)) $#)
		do
			print_array 1 $m $i $#
			if [ "${ARR[$m]}" -gt "${ARR[$i]}" ]
			then
				m=$i
			fi
		done
		if [ "$m" -ne "$p" ]
		then
			swap $m $p
			print_array 1 $p 0 $#
		fi
	done
}

function shell_sort()
{
	d=$#
	while [ "$d" -gt "1" ]
	do
		d=$(($d / 2))
		flag=0
		while [ "$flag" -eq "0" ]
		do
			flag=1
			for j in $(seq 1 $(($# - $d)))
			do
				i=$(($j + $d))
				print_array 1 $i $j $#
				if [ "${ARR[$j]}" -gt "${ARR[$i]}" ]
				then
					swap $j $i
					print_array 1 $j $i $#
					flag=0
				fi
			done
		done
	done
}

function gnome_sort()
{
	i=2
	while [ "$i" -le "$#" ]
	do
		print_array 1 $(($i - 1)) $i $#
		if [ "${ARR[$(($i - 1))]}" -le "${ARR[$i]}" ]
		then
			i=$(($i + 1))
		else
			swap $(($i - 1)) $i
			print_array 1 $i $(($i - 1)) $#
			if [ "$i" -gt "2" ]
			then
				i=$(($i - 1))
			else
				i=$(($i + 1))
			fi
		fi
	done
}

function main()
{
	SORT=$1
	shift
	read_array $@
	case $SORT in
		bubble)
			bubble_sort $@;;
		insertion)
			insertion_sort $@;;
		selection)
			selection_sort $@;;
		shell)
			shell_sort $@;;
		gnome)
			gnome_sort $@;;
		*)
			echo -e "Sort visualizations\nUsage: \033[1m$0\033[0m [ \033[1;32mbubble\033[0m | \033[1;32minsertion\033[0m | \033[1;32mselection\033[0m | \033[1;32mshell\033[0m | \033[1;32mgnome\033[0m ] \033[36mARRAY\033[0m"
			exit;;
	esac
	print_array 0 0 0 $#
	echo
}

main $@