//License: Expat(MIT)
//Chris Xiong 2017
const mrkcol=["#FFF","#F00","#0F0","#00F","#0FF","#F0F","#FF0","#F80","#F08","#0F8","#8F0","#80F","#08F"];
const ui={};
function min(a,b){return a<b?a:b;}
function max(a,b){return a>b?a:b;}
async function sleep(ms)
{
	return new Promise(resolve=>setTimeout(resolve,ms));
}
class ISort
{
	constructor(h)
	{
		this.executing=false;
		this.finished=false;
		this.step=false;
		this.h=h;
	}
	options()
	{
		return "";
	}
	async wait()
	{
		do{await sleep(5);}while(!this.step);
		this.step=false;
	}
	async execute(){}
};
class BubbleSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const h=this.h;
		let c=h.count;
		let swapped=false;
		do
		{
			swapped=false;
			for(let i=1;i<c;++i)
			{
				h.mark(i,1);h.mark(i-1,2);
				if(h.compar(i-1,i)==1)
				{
					h.swap(i-1,i);
					swapped=true;
				}
				await this.wait();
				h.mark(i,0);h.mark(i-1,0);
			}
			c=c-1;
		}
		while(swapped);
		this.finished=true;
	}
};
class SelectSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const h=this.h;
		const c=h.count;
		for(let i=0;i<c;++i)
		{
			let m=i;
			h.mark(i,1);
			for(let j=i+1;j<c;++j)
			{
				h.mark(j,3);
				if(h.get(j)<h.get(m))
				{
					if(m!=i)h.mark(m,0);
					m=j;h.mark(m,2);
				}
				await this.wait();
				if(m!==j)h.mark(j,0);
			}
			h.mark(i,0);h.mark(m,0);
			h.swap(i,m);
		}
		for(let i=0;i<c;++i)h.mark(i,0);
		this.finished=true;
	}
};
class InsertSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const h=this.h;
		const c=h.count;
		for(let i=1;i<c;++i)
		{
			let t=h.get(i);
			h.mark(i,1);
			for(let j=i-1;j>=0&&h.get(j)>t;--j)
			{
				h.mark(j,2);
				h.swap(j,j+1);
				await this.wait();
				h.mark(j,0);
			}
			h.mark(i,0);
		}
		this.finished=true;
	}
}
class CombSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const h=this.h;
		let swapped=false;
		let gap=h.count;
		while((gap>1)||swapped)
		{
			if(gap>1)gap=Math.floor(gap/1.3);
			swapped=false;
			for(let i=0;gap+i<h.count;++i)
			{
				h.mark(i,1);h.mark(i+gap,1);
				if(h.get(i)>h.get(i+gap))
				{
					h.swap(i,i+gap);
					swapped=true;
				}
				await this.wait();
				h.mark(i,0);h.mark(i+gap,0);
			}
		}
		this.finished=true;
	}
}
class ShellSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const gaps=[1073790977,268460033,67121153,16783361,4197377,
		1050113,262913,65921,16577,4193,1073,281,77,23,8,1];
		for(let g=0;g<gaps.length;++g)
		for(let cg=gaps[g],i=cg;i<h.count;++i)
		{
			h.mark(i,2);
			let t=h.get(i),j=i;
			for(let tv;j>=cg&&(tv=h.get(j-cg))>t;j-=cg)
			{
				let om=h.getmark(j);
				h.mark(j,1);
				h.set(j,tv);
				await this.wait();
				h.mark(j,om);
			}
			h.set(j,t);
			await this.wait();
			h.mark(i,0);
		}
		this.finished=true;
	}
}
class ShakerSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const h=this.h;
		for(let L=0,R=h.count-1,m=0;L<R;)
		{
			for(let i=R;i>L;--i)
			{
				h.mark(i-1,2);h.mark(i,1);
				if(h.compar(i-1,i)>0)
				{
					h.swap(i-1,i);
					m=i;
				}
				await this.wait();
				h.mark(i-1,0);h.mark(i,0);
			}
			L=m;
			for(let i=L;i<R;++i)
			{
				h.mark(i+1,2);h.mark(i,1);
				if(h.compar(i,i+1)>0)
				{
					h.swap(i+1,i);
					m=i;
				}
				await this.wait();
				h.mark(i+1,0);h.mark(i,0);
			}
			R=m;
		}
		this.finished=true;
	}
}
class QuickSort extends ISort
{
	constructor(h){super(h);}
	options()
	{
		return `{
			"optionlist":
			[
				{
					"dispname":"Pivot Selection",
					"opt":"pivot",
					"type":"enumsingle",
					"options":[
						"First",
						"Last",
						"Middle",
						"Random"
					],
					"defaultv":"2"
				}
			]
		}`;
	}
	async _sort(l,r)
	{
		const h=this.h;
		let i=l,j=r;
		let p=l;
		switch(Number(h.getopt("pivot")))
		{
			case 0:
			break;
			case 1:
				p=r;
			break;
			case 2:
				p=(l+r)>>1;
			break;
			case 3:
				p=Math.floor(Math.random()*(r+1-l))+l;
			break;
		}
		let x=h.get(p);
		h.mark(p,3);
		do
		{
			while(h.comparv(h.get(i),x)==-1)
			{
				++i;h.mark(i,1);
				await this.wait();h.mark(i,0);
			}
			while(h.comparv(h.get(j),x)== 1)
			{
				--j;h.mark(j,1);
				await this.wait();h.mark(j,0);
			}
			if(i<=j){h.swap(i,j);++i;--j;}
			h.mark(i,1);h.mark(j,1);
			await this.wait();
			h.mark(i,0);h.mark(j,0);
			h.mark(p,3);
		}
		while(i<=j);
		h.mark(p,0);
		if(l<j)await this._sort(l,j);
		if(i<r)await this._sort(i,r);
	}
	async execute()
	{
		this.executing=true;
		await this._sort(0,this.h.count-1);
		this.finished=true;
	}
}
class MergeSort extends ISort
{
	constructor(h){super(h);}
	async merge(L,R,M)
	{
		this.h.mark(L,2);this.h.mark(R-1,2);
		this.h.mark(M,3);
		let t=[];
		let i=L,j=M;
		while(i<M&&j<R)
		{
			let a=this.h.get(i);
			let b=this.h.get(j);
			t.push(
				this.h.comparv(a,b)<0?
				(++i,a):
				(++j,b)
			);
			this.h.mark(i,1);this.h.mark(j,1);
			await this.wait();
			this.h.mark(i,0);this.h.mark(j,0);
			this.h.mark(L,2);this.h.mark(R-1,2);
			this.h.mark(M,3);
		}
		while(i<M){t.push(this.h.get(i++));await this.wait();}
		while(j<R){t.push(this.h.get(j++));await this.wait();}
		for(i=0;i<R-L;++i)
		{
			this.h.set(L+i,t[i]);
			let om=this.h.getmark(L+i);
			this.h.mark(L+i,1);
			await this.wait();
			this.h.mark(L+i,om);
		}
		this.h.mark(L,0);this.h.mark(R-1,0);
		this.h.mark(M,0);
	}
	async _sort(L,R)
	{
		if(L+1>=R)return;
		const M=(L+R)>>1;
		await this._sort(L,M);
		await this._sort(M,R);
		await this.merge(L,R,M);
	}
	async execute()
	{
		this.executing=true;
		await this._sort(0,this.h.count);
		this.finished=true;
	}
}
class HeapSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const h=this.h;
		let n=h.count,le=n>>1;
		for(let i=le;i<n;++i)h.mark(i,Math.floor(Math.log(i+1)/Math.log(2))+2);
		for(;;)
		{
			if(le>0)--le;
			else
			{
				if(!--n)break;
				h.swap(0,n);
				h.mark(n,1);
				if(n+1<h.count)h.mark(n+1,0);
				await this.wait();
			}
			let par=le,ch=(le<<1)|1;
			while(ch<n)
			{
				if(ch+1<n&&h.compar(ch+1,ch)>0)++ch;
				if(h.compar(ch,par)>0)
				{
					h.swap(ch,par);
					par=ch;ch=(par<<1)|1;
				}else break;
				await this.wait();
			}
			h.mark(le,Math.floor(Math.log(le+1)/Math.log(2))+2);
			await this.wait();
		}
		this.finished=true;
	}
}
class LSDRadixSort extends ISort
{
	constructor(h){super(h);}
	async execute()
	{
		this.executing=true;
		const R=4;
		const pm=Math.ceil(Math.log(h.maxval+1)/Math.log(R));
		for(let p=0;p<pm;++p)
		{
			let base=Math.round(Math.pow(R,p));
			let c=[];for(let i=0;i<R;++i)c[i]=0;
			let cpy=[];
			for(let i=0;i<h.count;++i)
			{
				h.mark(i,1);
				cpy[i]=h.get(i);
				let r=Math.floor(cpy[i]/base)%R;
				++c[r];
				await this.wait();
				h.mark(i,0);
			}
			let ps=[];ps.push(0);
			for(let i=0;i<R;++i)
			ps[i+1]=ps[i]+c[i];
			for(let i=0;i<ps.length-1;++i)
			{
				if(ps[i]>=h.count)continue;
				h.mark(ps[i],3);
			}
			for(let i=0;i<h.count;++i)
			{
				let r=Math.floor(cpy[i]/base)%R;
				let om=h.getmark(ps[r]);
				h.set(ps[r],cpy[i]);
				h.mark(ps[r],1);
				await this.wait();
				h.mark(ps[r]++,om);
			}
			for(let i=0;i<h.count;++i)h.mark(i,0);
		}
		this.finished=true;
	}
}
class MSDRadixSort extends ISort
{
	constructor(h){super(h);}
	async _sort(L,R,dpt)
	{
		const Rdx=4;
		const h=this.h;
		h.mark(L,2);h.mark(R-1,2);
		const pm=Math.floor(Math.log(h.maxval+1)/Math.log(Rdx));
		let base=Math.round(Math.pow(Rdx,pm-dpt));
		let c=[];for(let i=0;i<Rdx;++i)c[i]=0;
		for(let i=L;i<R;++i)
		{
			let om=h.getmark(i);
			h.mark(i,1);
			let r=Math.floor(h.get(i)/base)%Rdx;
			++c[r];
			await this.wait();
			h.mark(i,om);
		}
		let ps=[];ps[0]=c[0];
		for(let i=1;i<Rdx;++i)
		ps[i]=ps[i-1]+c[i];
		for(let i=0;i<ps.length;++i)
		{
			if(ps[i]===0)continue;
			h.mark(L+ps[i]-1,3);
		}
		for(let i=0,j;i<(R-L);)
		{
			while((j=--ps[Math.floor(h.get(L+i)/base)%Rdx])>i)
			{
				h.swap(L+i,L+j);
				await this.wait();
			}
			i+=c[Math.floor(h.get(L+i)/base)%Rdx];
		}
		for(let i=0;i<h.count;++i)h.mark(i,0);
		if(dpt+1>pm)return;
		let s=L;
		for(let i=0;i<Rdx;++i)
		{
			if(c[i]>1)
			await this._sort(s,s+c[i],dpt+1);
			s+=c[i];
		}
	}
	async execute()
	{
		this.executing=true;
		await this._sort(0,h.count,0);
		this.finished=true;
	}
}
class SortHypervisor
{
	constructor()
	{
		this.ctx=ui.cvs.getContext("2d");
		this.w=ui.cvs.width;
		this.h=ui.cvs.height;
		this.ctx.clearRect(0,0,this.w,this.h);
		this.ctx.lineWidth=window.devicePixelRatio.toString();
		window.AudioContext=window.AudioContext||window.webkitAudioContext;
		this.actx=new AudioContext();
		this.dly=20;
		this.reset(100);
	}
	reset(c)
	{
		this.raccess=0;
		this.waccess=0;
		this.count=c;
		this.bin=[];
		this.mrk=[];
		this.algo=null;
		this.initalgo();
		this.breakexec=false;
		for(let i=0;i<this.count;++i)
		{this.bin[i]=i+1;this.mrk[i]=0;}
		this.maxval=this.count+1;
	}
	shuffle()
	{
		this.breakexec=true;
		this.initalgo();
		for(let i=0;i<this.count;++i)
		{this.bin[i]=i+1;this.mrk[i]=0;}
		this.maxval=this.count+1;
		switch(ui.sdat.value)
		{
			case "asc":
			break;
			case "dec":
				for(let i=0;i<this.count;++i)
				this.bin[i]=this.count-i;
			break;
			case "rnd":
			case "cub":
			case "qui":
				let pow=(ui.sdat.value==="cub"?3:5);
				if(ui.sdat.value!="rnd")
				for(let i=0;i<this.count;++i)
				this.bin[i]=Math.floor((Math.pow((2.*i/this.count-1),pow)+1)*this.count/2)+1;
				this.maxval=this.bin[this.count-1];
				for(let i=this.count-1;i>0;--i)
				{
					let r=Math.floor(Math.random()*(i+1));
					let t=this.bin[i];
					this.bin[i]=this.bin[r];
					this.bin[r]=t;
				}

			break;
		}
		this.fullredraw();
	}
	swap(ida,idb)
	{
		this.raccess+=2;
		this.waccess+=2;
		let t=this.bin[ida];
		this.bin[ida]=this.bin[idb];
		this.bin[idb]=t;
		this.singleredraw(ida);
		this.singleredraw(idb);
	}
	get(id)
	{
		++this.raccess;
		this.sound(this.bin[id]/this.count*1100+132);
		return this.bin[id];
	}
	set(id,v)
	{
		++this.waccess;
		this.bin[id]=v;
		this.sound(this.bin[id]/this.count*1100+132);
		this.singleredraw(id);
	}
	comparv(a,b){return a<b?-1:a>b?1:0;}
	compar(ida,idb)
	{
		let a=this.get(ida),b=this.get(idb);
		return this.comparv(a,b);
	}
	getmark(id){return this.mrk[id];}
	mark(id,m){
		this.mrk[id]=m;
		this.singleredraw(id);
	}
	fullredraw()
	{
		const w=this.w,h=this.h,n=this.count;
		this.ctx.clearRect(0,0,w,h);
		for(let i=0;i<n;++i)
		{
			this.ctx.fillStyle=mrkcol[this.mrk[i]];
			this.ctx.fillRect(i*w/n,(n+1-this.bin[i])/n*h,w/n,this.bin[i]/n*h);
			this.ctx.strokeRect(i*w/n,(n+1-this.bin[i])/n*h,w/n,this.bin[i]/n*h);
		}
	}
	singleredraw(id)
	{
		const w=this.w,h=this.h,n=this.count;
		this.ctx.clearRect(id*w/n-w/n*0.5,0,w/n*2,h);
		for(let i=max(id-1,0);i<=min(id+1,n-1);++i)
		{
			this.ctx.fillStyle=mrkcol[this.mrk[i]];
			this.ctx.fillRect(i*w/n,(n+1-this.bin[i])/n*h,w/n,this.bin[i]/n*h);
			this.ctx.strokeRect(i*w/n,(n+1-this.bin[i])/n*h,w/n,this.bin[i]/n*h);
		}
	}
	initalgo(algochanged)
	{
		this.raccess=this.waccess=0;
		ui.lbra.innerHTML="0";
		ui.lbwa.innerHTML="0";
		this.algo=eval('new '+ui.salg.value+'(this);');
		if(algochanged)
		{
			this.algoopt=new Map();
			while(ui.wopt.hasChildNodes())ui.wopt.removeChild(ui.wopt.lastChild);
			if(!this.algo.options().length)return;
			let ol=JSON.parse(this.algo.options()).optionlist;
			for(let i=0;i<ol.length;++i)
			{
				let ell=document.createElement('label');
				ell.htmlFor=ol[i].opt;
				ell.innerHTML=ol[i].dispname;
				ui.wopt.appendChild(ell);
				switch(ol[i].type)
				{
					case "enumsingle":
						let elo=document.createElement('select');
						this.algoopt.set(ol[i].opt,{"el":elo,"type":ol[i].type});
						elo.id=ol[i].opt;
						ui.wopt.appendChild(elo);
						for(let j=0;j<ol[i].options.length;++j)
						{
							let eloc=document.createElement('option');
							eloc.text=ol[i].options[j];
							eloc.value=j;
							if(j==Number(ol[i].defaultv))
							eloc.selected="selected";
							elo.appendChild(eloc);
						}
						ui.wopt.appendChild(elo);
					break;
				}
			}
		}
	}
	async execute()
	{
		if(!this.algo.executing||this.algo.finished)
		{
			this.initalgo();
			this.algo.execute();
		}
		this.breakexec=false;
		while(!this.algo.finished&&!this.breakexec)
		{
			await sleep(this.dly);
			this.algo.step=true;
			ui.lbra.innerHTML=this.raccess;
			ui.lbwa.innerHTML=this.waccess;
		}
		if(this.algo.finished)
		{
			let last=0,err=false;
			for(let i=0;i<this.count;++i)
			{
				let t=this.get(i);
				if(t<last){if(!err)alert("The algorithm failed to sort the array...");err=true;}
				last=t;
				this.mark(i,2);
				await sleep(10);
			}
			for(let i=0;i<this.count;++i)this.mark(i,0);
		}
	}
	step()
	{
		if(!this.algo.executing||this.algo.finished)
		{
			this.initalgo();
			this.algo.execute();
		}
		else this.algo.step=true;
		this.breakexec=true;
		ui.lbra.innerHTML=this.raccess;
		ui.lbwa.innerHTML=this.waccess;
	}
	changealgo()
	{
		this.breakexec=true;
		this.initalgo(true);
		this.shuffle();
	}
	getopt(o)
	{
		switch(this.algoopt.get(o).type)
		{
			case "enumsingle":
				return this.algoopt.get(o).el.value;
			break;
		}
	}
	sound(freq)
	{
		let o=this.actx.createOscillator();
		let g=this.actx.createGain();
		o.connect(g);g.connect(this.actx.destination);
		o.frequency.value=freq;o.type="triangle";
		let t=this.actx.currentTime;
		o.start(0);
		g.gain.setValueAtTime(0,0);
		g.gain.linearRampToValueAtTime(0.1,t+0.005)
		g.gain.linearRampToValueAtTime(0,t+0.105);
		o.stop(t+0.1);
	}
};
let h=null;
function init()
{
	ui.cvs=document.getElementById("cvs");
	ui.rspd=document.getElementById("spd");
	ui.rcnt=document.getElementById("count");
	ui.wopt=document.getElementById("optw");
	ui.salg=document.getElementById("sel");
	ui.sdat=document.getElementById("data");
	ui.lbra=document.getElementById("racc");
	ui.lbwa=document.getElementById("wacc");
	ui.lbcnt=document.getElementById("lbcnt");
	ui.lbspd=document.getElementById("lbspd");
	if(!window.devicePixelRatio)window.devicePixelRatio=1;
	if(ui.cvs.width>window.innerWidth*0.95)ui.cvs.width=window.innerWidth*0.95;
	ui.cvs.height=ui.cvs.width/16*9;
	if(ui.cvs.height>window.innerHeight*0.72)
	{
		ui.cvs.height=window.innerHeight*0.72;
		ui.cvs.width=ui.cvs.height/9*16;
	}
	ui.cvs.style.width=ui.cvs.width+"px";
	ui.cvs.style.height=ui.cvs.height+"px";
	ui.cvs.width=ui.cvs.width*window.devicePixelRatio;
	ui.cvs.height=ui.cvs.height*window.devicePixelRatio;
	ui.rspd.onchange=()=>{h.dly=Number(ui.rspd.value);}
	ui.rcnt.onchange=()=>{h.reset(Number(ui.rcnt.value));h.fullredraw();}
	ui.rspd.oninput=()=>{ui.lbspd.innerHTML=ui.rspd.value+"ms";}
	ui.rcnt.oninput=()=>{ui.lbcnt.innerHTML=ui.rcnt.value;}
	ui.salg.onchange=()=>{h.changealgo();}
	h=new SortHypervisor();
	h.shuffle();
	h.fullredraw();
}