summaryrefslogtreecommitdiff
path: root/sound-of-sorting
diff options
context:
space:
mode:
authorGravatar Chris Xiong <chirs241097@gmail.com> 2019-02-10 11:16:07 +0800
committerGravatar Chris Xiong <chirs241097@gmail.com> 2019-02-10 11:16:07 +0800
commit9d3c8c0e6e1a7ba43bf3dc19350d1dca68b657a3 (patch)
tree339de0698c13e1763d3361d70fb1266621025c91 /sound-of-sorting
downloadweb-9d3c8c0e6e1a7ba43bf3dc19350d1dca68b657a3.tar.xz
Initial commit.
Diffstat (limited to 'sound-of-sorting')
-rw-r--r--sound-of-sorting/index.html130
-rw-r--r--sound-of-sorting/main.js730
-rw-r--r--sound-of-sorting/main_babel.js1
3 files changed, 861 insertions, 0 deletions
diff --git a/sound-of-sorting/index.html b/sound-of-sorting/index.html
new file mode 100644
index 0000000..7dc466d
--- /dev/null
+++ b/sound-of-sorting/index.html
@@ -0,0 +1,130 @@
+<!DOCTYPE html>
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
+<meta name="viewport" content="width=device-width, initial-scale=1">
+<title>Chrisoft::Sound of Sorting</title>
+<link rel="icon" href="../favicon.png">
+<script type="text/javascript" src="main.js"></script>
+<style>
+button{
+ border:none;
+ color:white;
+ padding:0.5em 2em;
+ text-align:center;
+ background-color:#44AA44;
+ -webkit-transition-duration: 0.4s;
+ transition-duration: 0.4s;
+}
+button:hover{
+ background-color:#66CC66;
+}
+input[type=range]{
+ -webkit-appearance:none;
+}
+input[type=range]:focus{
+ outline:none;
+}
+input[type=range]::-webkit-slider-runnable-track{
+ width:100%;
+ height:8.4px;
+ animate:0.2s;
+ box-shadow:1px 1px 1px #000000, 0px 0px 1px #0d0d0d;
+ background:#44AA44;
+ border-radius:1.3px;
+ border:0.2px solid #010101;
+}
+input[type=range]::-moz-range-track{
+ width:100%;
+ height:8.4px;
+ animate:0.2s;
+ box-shadow:1px 1px 1px #000000, 0px 0px 1px #0d0d0d;
+ background:#44AA44;
+ border-radius:1.3px;
+ border:0.2px solid #010101;
+}
+input[type=range]::-webkit-slider-thumb{
+ box-shadow:1px 1px 1px #000000, 0px 0px 1px #0d0d0d;
+ border:1px solid #000000;
+ height:24px;
+ width:12px;
+ border-radius:1px;
+ background:#ffffff;
+ -webkit-appearance:none;
+ margin-top:-8px;
+}
+input[type=range]::-moz-range-thumb{
+ box-shadow:1px 1px 1px #000000, 0px 0px 1px #0d0d0d;
+ border:1px solid #000000;
+ height:24px;
+ width:12px;
+ border-radius:1px;
+ background:#ffffff;
+ -webkit-appearance:none;
+ margin-top:-8px;
+}
+input[type=range]:focus::-webkit-slider-runnable-track{
+ background:#66CC66;
+}
+input[type=range]:focus::-moz-range-track{
+ background:#66CC66;
+}
+select{
+ background-color:#EEE;
+ border:1px #AAA solid;
+ padding:0.2em 0.2em;
+}
+</style>
+</head>
+<body onload="init()">
+ <div style="text-align:center;">
+ <canvas id="cvs" width="1600" height="600"></canvas><br>
+ <form>
+ <label for="sel">Algorithm</label>
+ <select id="sel">
+ <option value="BubbleSort">Bubble Sort</option>
+ <option value="SelectSort">Selection Sort</option>
+ <option value="InsertSort">Insertion Sort</option>
+ <option value="ShakerSort">Cocktail Shaker Sort</option>
+ <option value="CombSort">Comb Sort</option>
+ <option value="ShellSort">Shell Sort</option>
+ <option value="QuickSort">Quick Sort</option>
+ <option value="MergeSort">Merge Sort</option>
+ <option value="HeapSort">Heap Sort</option>
+ <option value="LSDRadixSort">LSD Radix Sort</option>
+ <option value="MSDRadixSort">MSD Radix Sort</option>
+ </select>
+ &nbsp;&nbsp;&nbsp;&nbsp;
+ <label for="data">Data to sort</label>
+ <select id="data">
+ <option value="rnd">Random Shuffle</option>
+ <option value="asc">Ascending</option>
+ <option value="dec">Descending</option>
+ <option value="cub">Shuffled Cubic</option>
+ <option value="qui">Shuffled Quintic</option>
+ </select>
+ <br>
+ <div style="margin-top:.5em;margin-bottom:.1em;">
+ <button type="button" onclick="h.shuffle();">Reset</button>
+ <button type="button" onclick="h.execute();">Run</button>
+ <button type="button" onclick="h.step();">Step</button>
+ </div>
+ <br>
+ <label for="count">Array size:</label>
+ <input type="range" id="count" min="1" max="1024" value="100" step="1">
+ <span id="lbcnt">100</span>
+ &nbsp;&nbsp;&nbsp;&nbsp;
+ <label for="spd">Delay between steps:</label>
+ <input type="range" id="spd" min="5" max="200" value="20" step="5">
+ <span id="lbspd">20ms</span>
+ </form>
+ <p>
+ Read Access: <span id="racc"></span><br>
+ Write Access: <span id="wacc"></span>
+ </p>
+ <form>
+ <fieldset id="optw" style="border:none;">
+ </fieldset>
+ <form>
+ </div>
+</body>
diff --git a/sound-of-sorting/main.js b/sound-of-sorting/main.js
new file mode 100644
index 0000000..f5fe079
--- /dev/null
+++ b/sound-of-sorting/main.js
@@ -0,0 +1,730 @@
+//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();
+}
diff --git a/sound-of-sorting/main_babel.js b/sound-of-sorting/main_babel.js
new file mode 100644
index 0000000..8c79dbb
--- /dev/null
+++ b/sound-of-sorting/main_babel.js
@@ -0,0 +1 @@
+"use strict";var _createClass=function(){function d(e,f){for(var p,k=0;k<f.length;k++)p=f[k],p.enumerable=p.enumerable||!1,p.configurable=!0,"value"in p&&(p.writable=!0),Object.defineProperty(e,p.key,p)}return function(e,f,k){return f&&d(e.prototype,f),k&&d(e,k),e}}(),sleep=function(){var d=_asyncToGenerator(regeneratorRuntime.mark(function e(f){return regeneratorRuntime.wrap(function(p){for(;;)switch(p.prev=p.next){case 0:return p.abrupt("return",new Promise(function(q){return setTimeout(q,f)}));case 1:case"end":return p.stop();}},e,this)}));return function(){return d.apply(this,arguments)}}();function _possibleConstructorReturn(d,e){if(!d)throw new ReferenceError("this hasn't been initialised - super() hasn't been called");return e&&("object"==typeof e||"function"==typeof e)?e:d}function _inherits(d,e){if("function"!=typeof e&&null!==e)throw new TypeError("Super expression must either be null or a function, not "+typeof e);d.prototype=Object.create(e&&e.prototype,{constructor:{value:d,enumerable:!1,writable:!0,configurable:!0}}),e&&(Object.setPrototypeOf?Object.setPrototypeOf(d,e):d.__proto__=e)}function _classCallCheck(d,e){if(!(d instanceof e))throw new TypeError("Cannot call a class as a function")}function _asyncToGenerator(d){return function(){var e=d.apply(this,arguments);return new Promise(function(f,k){function p(q,s){try{var u=e[q](s),y=u.value}catch(z){return void k(z)}return u.done?void f(y):Promise.resolve(y).then(function(z){p("next",z)},function(z){p("throw",z)})}return p("next")})}}var mrkcol=["#FFF","#F00","#0F0","#00F","#0FF","#F0F","#FF0","#F80","#F08","#0F8","#8F0","#80F","#08F"],ui={};function min(d,e){return d<e?d:e}function max(d,e){return d>e?d:e}var ISort=function(){function d(e){_classCallCheck(this,d),this.finished=!1,this.step=!1,this.h=e}return _createClass(d,[{key:"options",value:function options(){return""}},{key:"wait",value:function(){var f=_asyncToGenerator(regeneratorRuntime.mark(function k(){return regeneratorRuntime.wrap(function(q){for(;;)switch(q.prev=q.next){case 0:return q.next=2,sleep(10);case 2:if(!this.step){q.next=0;break}case 3:this.step=!1;case 4:case"end":return q.stop();}},k,this)}));return function e(){return f.apply(this,arguments)}}()},{key:"execute",value:function(){var f=_asyncToGenerator(regeneratorRuntime.mark(function k(){return regeneratorRuntime.wrap(function(q){for(;;)switch(q.prev=q.next){case 0:case"end":return q.stop();}},k,this)}));return function e(){return f.apply(this,arguments)}}()}]),d}();var BubbleSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){var q,s,u,y;return regeneratorRuntime.wrap(function(A){for(;;)switch(A.prev=A.next){case 0:q=this.h,s=q.count,u=!1;case 3:u=!1,y=1;case 5:if(!(y<s)){A.next=16;break}return q.mark(y,1),q.mark(y-1,2),1==q.compar(y-1,y)&&(q.swap(y-1,y),u=!0),A.next=11,this.wait();case 11:q.mark(y,0),q.mark(y-1,0);case 13:++y,A.next=5;break;case 16:--s;case 17:if(u){A.next=3;break}case 18:this.finished=!0;case 19:case"end":return A.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort);var SelectSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){var q,s,u,y,z,A;return regeneratorRuntime.wrap(function(C){for(;;)switch(C.prev=C.next){case 0:q=this.h,s=q.count,u=0;case 3:if(!(u<s)){C.next=22;break}y=u,q.mark(u,1),z=u+1;case 7:if(!(z<s)){C.next=16;break}return q.mark(z,3),q.get(z)<q.get(y)&&(y!=u&&q.mark(y,0),y=z,q.mark(y,2)),C.next=12,this.wait();case 12:y!==z&&q.mark(z,0);case 13:++z,C.next=7;break;case 16:q.mark(u,0),q.mark(y,0),q.swap(u,y);case 19:++u,C.next=3;break;case 22:for(A=0;A<s;++A)q.mark(A,0);this.finished=!0;case 24:case"end":return C.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort);var InsertSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){var q,s,u,y,z;return regeneratorRuntime.wrap(function(B){for(;;)switch(B.prev=B.next){case 0:q=this.h,s=q.count,u=1;case 3:if(!(u<s)){B.next=20;break}y=q.get(u),q.mark(u,1),z=u-1;case 7:if(!(0<=z&&q.get(z)>y)){B.next=16;break}return q.mark(z,2),q.swap(z,z+1),B.next=12,this.wait();case 12:q.mark(z,0);case 13:--z,B.next=7;break;case 16:q.mark(u,0);case 17:++u,B.next=3;break;case 20:this.finished=!0;case 21:case"end":return B.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort),ShakerSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){var q,s,u,y,z,A;return regeneratorRuntime.wrap(function(C){for(;;)switch(C.prev=C.next){case 0:q=this.h,s=0,u=q.count-1,y=0;case 2:if(!(s<u)){C.next=31;break}z=u;case 4:if(!(z>s)){C.next=15;break}return q.mark(z-1,2),q.mark(z,1),0<q.compar(z-1,z)&&(q.swap(z-1,z),y=z),C.next=10,this.wait();case 10:q.mark(z-1,0),q.mark(z,0);case 12:--z,C.next=4;break;case 15:s=y,A=s;case 17:if(!(A<u)){C.next=28;break}return q.mark(A+1,2),q.mark(A,1),0<q.compar(A,A+1)&&(q.swap(A+1,A),y=A),C.next=23,this.wait();case 23:q.mark(A+1,0),q.mark(A,0);case 25:++A,C.next=17;break;case 28:u=y;case 29:C.next=2;break;case 31:this.finished=!0;case 32:case"end":return C.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort),QuickSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"options",value:function options(){return"{\n\t\t\t\"optionlist\":\n\t\t\t[\n\t\t\t\t{\n\t\t\t\t\t\"dispname\":\"Pivot Selection\",\n\t\t\t\t\t\"opt\":\"pivot\",\n\t\t\t\t\t\"type\":\"enumsingle\",\n\t\t\t\t\t\"options\":[\n\t\t\t\t\t\t\"First\",\n\t\t\t\t\t\t\"Last\",\n\t\t\t\t\t\t\"Middle\",\n\t\t\t\t\t\t\"Random\"\n\t\t\t\t\t],\n\t\t\t\t\t\"default\":\"2\"\n\t\t\t\t}\n\t\t\t]\n\t\t}"}},{key:"_sort",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(q,s){var u,y,z,A;return regeneratorRuntime.wrap(function(C){for(;;)switch(C.prev=C.next){case 0:u=this.h,y=q,z=s,A=u.get(q+s>>1),u.mark(q+s>>1,3);case 4:if(-1!=u.comparv(u.get(y),A)){C.next=12;break}return++y,u.mark(y,1),C.next=9,this.wait();case 9:u.mark(y,0),C.next=4;break;case 12:if(1!=u.comparv(u.get(z),A)){C.next=20;break}return--z,u.mark(z,1),C.next=17,this.wait();case 17:u.mark(z,0),C.next=12;break;case 20:return y<=z&&(u.swap(y,z),++y,--z),u.mark(y,1),u.mark(z,1),C.next=25,this.wait();case 25:u.mark(y,0),u.mark(z,0),u.mark(q+s>>1,3);case 28:if(y<=z){C.next=4;break}case 29:if(u.mark(q+s>>1,0),!(q<z)){C.next=33;break}return C.next=33,this._sort(q,z);case 33:if(!(y<s)){C.next=36;break}return C.next=36,this._sort(y,s);case 36:case"end":return C.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()},{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){return regeneratorRuntime.wrap(function(s){for(;;)switch(s.prev=s.next){case 0:return s.next=2,this._sort(0,this.h.count-1);case 2:this.finished=!0;case 3:case"end":return s.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort),MergeSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"merge",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(q,s,u){var y,z,A,B,C;return regeneratorRuntime.wrap(function(E){for(;;)switch(E.prev=E.next){case 0:this.h.mark(q,2),this.h.mark(s-1,2),this.h.mark(u,3),y=[],z=q,A=u;case 5:if(!(z<u&&A<s)){E.next=20;break}return B=this.h.get(z),C=this.h.get(A),y.push(0>this.h.comparv(B,C)?(++z,B):(++A,C)),this.h.mark(z,1),this.h.mark(A,1),E.next=13,this.wait();case 13:this.h.mark(z,0),this.h.mark(A,0),this.h.mark(q,2),this.h.mark(s-1,2),this.h.mark(u,3),E.next=5;break;case 20:if(!(z<u)){E.next=26;break}return y.push(this.h.get(z++)),E.next=24,this.wait();case 24:E.next=20;break;case 26:if(!(A<s)){E.next=32;break}return y.push(this.h.get(A++)),E.next=30,this.wait();case 30:E.next=26;break;case 32:z=0;case 33:if(!(z<s-q)){E.next=40;break}return this.h.set(q+z,y[z]),E.next=37,this.wait();case 37:++z,E.next=33;break;case 40:this.h.mark(q,0),this.h.mark(s-1,0),this.h.mark(u,0);case 43:case"end":return E.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()},{key:"_sort",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(q,s){var u;return regeneratorRuntime.wrap(function(z){for(;;)switch(z.prev=z.next){case 0:if(!(q+1>=s)){z.next=2;break}return z.abrupt("return");case 2:return u=q+s>>1,z.next=5,this._sort(q,u);case 5:return z.next=7,this._sort(u,s);case 7:return z.next=9,this.merge(q,s,u);case 9:case"end":return z.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()},{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){return regeneratorRuntime.wrap(function(s){for(;;)switch(s.prev=s.next){case 0:return s.next=2,this._sort(0,this.h.count);case 2:this.finished=!0;case 3:case"end":return s.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort),HeapSort=function(d){function e(f){return _classCallCheck(this,e),_possibleConstructorReturn(this,(e.__proto__||Object.getPrototypeOf(e)).call(this,f))}return _inherits(e,d),_createClass(e,[{key:"execute",value:function(){var k=_asyncToGenerator(regeneratorRuntime.mark(function p(){var q,s,u,y,z,A;return regeneratorRuntime.wrap(function(C){for(;;)switch(C.prev=C.next){case 0:for(q=this.h,s=q.count,u=s>>1,y=u;y<s;++y)q.mark(y,Math.floor(Math.log(y+1)/Math.log(2))+2);case 3:if(!(0<u)){C.next=7;break}--u,C.next=14;break;case 7:if(--s){C.next=9;break}return C.abrupt("break",31);case 9:return q.swap(0,s),q.mark(s,1),s+1<q.count&&q.mark(s+1,0),C.next=14,this.wait();case 14:z=u,A=1|u<<1;case 15:if(!(A<s)){C.next=28;break}if(A+1<s&&0<q.compar(A+1,A)&&++A,!(0<q.compar(A,z))){C.next=23;break}q.swap(A,z),z=A,A=1|z<<1,C.next=24;break;case 23:return C.abrupt("break",28);case 24:return C.next=26,this.wait();case 26:C.next=15;break;case 28:q.mark(u,Math.floor(Math.log(u+1)/Math.log(2))+2);case 29:C.next=3;break;case 31:this.finished=!0;case 32:case"end":return C.stop();}},p,this)}));return function f(){return k.apply(this,arguments)}}()}]),e}(ISort),SortHypervisor=function(){function SortHypervisor(){_classCallCheck(this,SortHypervisor),this.ctx=document.getElementById("cvs").getContext("2d"),this.w=document.getElementById("cvs").width,this.h=document.getElementById("cvs").height,this.ctx.clearRect(0,0,this.w,this.h),this.ctx.lineWidth=window.devicePixelRatio.toString(),this.actx=new AudioContext,this.dly=20,this.reset(100)}return _createClass(SortHypervisor,[{key:"reset",value:function reset(d){this.raccess=0,this.waccess=0,this.count=d,this.bin=[],this.mrk=[],this.algo=null,this.breakexec=!1;for(var e=0;e<this.count;++e)this.bin[e]=e+1,this.mrk[e]=0}},{key:"shuffle",value:function shuffle(){this.breakexec=!0,this.algo=null;for(var d=0;d<this.count;++d)this.bin[d]=d+1,this.mrk[d]=0;for(var e=this.count-1;0<e;--e){var f=Math.floor(Math.random()*(e+1)),k=this.bin[e];this.bin[e]=this.bin[f],this.bin[f]=k}this.fullredraw()}},{key:"swap",value:function swap(d,e){this.raccess+=2,this.waccess+=2;var f=this.bin[d];this.bin[d]=this.bin[e],this.bin[e]=f,this.singleredraw(d),this.singleredraw(e)}},{key:"get",value:function get(d){return++this.raccess,this.sound(2200*(this.bin[d]/this.count)+55),this.bin[d]}},{key:"set",value:function set(d,e){++this.waccess,this.bin[d]=e,this.singleredraw(d)}},{key:"comparv",value:function comparv(d,e){return d<e?-1:d>e?1:0}},{key:"compar",value:function compar(d,e){var f=this.get(d),k=this.get(e);return this.comparv(f,k)}},{key:"mark",value:function mark(d,e){this.mrk[d]=e,this.singleredraw(d)}},{key:"fullredraw",value:function fullredraw(){var d=this.w,e=this.h,f=this.count;this.ctx.clearRect(0,0,d,e);for(var k=0;k<f;++k)this.ctx.fillStyle=mrkcol[this.mrk[k]],this.ctx.fillRect(k*d/f,(f+1-this.bin[k])/f*e,d/f,this.bin[k]/f*e),this.ctx.strokeRect(k*d/f,(f+1-this.bin[k])/f*e,d/f,this.bin[k]/f*e)}},{key:"singleredraw",value:function singleredraw(d){var e=this.w,f=this.h,k=this.count;this.ctx.clearRect(d*e/k-0.5*(e/k),0,2*(e/k),f);for(var p=max(d-1,0);p<=min(d+1,k-1);++p)this.ctx.fillStyle=mrkcol[this.mrk[p]],this.ctx.fillRect(p*e/k,(k+1-this.bin[p])/k*f,e/k,this.bin[p]/k*f),this.ctx.strokeRect(p*e/k,(k+1-this.bin[p])/k*f,e/k,this.bin[p]/k*f)}},{key:"execute",value:function(){var _ref14=_asyncToGenerator(regeneratorRuntime.mark(function _callee14(){var i,_i4;return regeneratorRuntime.wrap(function(_context14){for(;;)switch(_context14.prev=_context14.next){case 0:(null===this.algo||this.algo.finished)&&(this.algo=eval("new "+document.getElementById("sel").value+"(this)"),this.algo.execute()),this.breakexec=!1;case 2:if(this.algo.finished||this.breakexec){_context14.next=8;break}return _context14.next=5,sleep(this.dly);case 5:this.algo.step=!0,_context14.next=2;break;case 8:if(!this.algo.finished){_context14.next=19;break}i=0;case 10:if(!(i<this.count)){_context14.next=18;break}return this.get(i),this.mark(i,2),_context14.next=15,sleep(10);case 15:++i,_context14.next=10;break;case 18:for(_i4=0;_i4<this.count;++_i4)this.mark(_i4,0);case 19:case"end":return _context14.stop();}},_callee14,this)}));return function execute(){return _ref14.apply(this,arguments)}}()},{key:"step",value:function step(){null===this.algo||this.algo.finished?(this.algo=eval("new "+document.getElementById("sel").value+"(this)"),this.algo.execute()):this.algo.step=!0,this.breakexec=!0}},{key:"sound",value:function sound(d){var e=this.actx.createOscillator(),f=this.actx.createGain();e.connect(f),f.connect(this.actx.destination),e.frequency.value=d,e.type="sine";var k=this.actx.currentTime;e.start(0),f.gain.setValueAtTime(0.2,0),f.gain.linearRampToValueAtTime(0,k+0.1),e.stop(k+0.1)}}]),SortHypervisor}();var h=null;function init(){ui.cvs=document.getElementById("cvs"),ui.rspd=document.getElementById("spd"),ui.wopt=document.getElementById("optdiv"),window.devicePixelRatio||(window.devicePixelRatio=1),ui.cvs.style.width=ui.cvs.width+"px",ui.cvs.style.height=ui.cvs.height+"px",ui.cvs.width*=window.devicePixelRatio,ui.cvs.height*=window.devicePixelRatio,ui.rspd.onchange=function(){h.dly=+ui.rspd.value},h=new SortHypervisor,h.fullredraw()}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 09:52:47 +0000