diff options
Diffstat (limited to 'main.js')
-rw-r--r-- | main.js | 729 |
1 files changed, 729 insertions, 0 deletions
@@ -0,0 +1,729 @@ +//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.fullredraw(); +} |