Chrisoft::Sound of Sorting

From 9d3c8c0e6e1a7ba43bf3dc19350d1dca68b657a3 Mon Sep 17 00:00:00 2001 From: Chris Xiong Date: Sun, 10 Feb 2019 11:16:07 +0800 Subject: Initial commit. --- sound-of-sorting/index.html | 130 ++++++++ sound-of-sorting/main.js | 730 +++++++++++++++++++++++++++++++++++++++++ sound-of-sorting/main_babel.js | 1 + 3 files changed, 861 insertions(+) create mode 100644 sound-of-sorting/index.html create mode 100644 sound-of-sorting/main.js create mode 100644 sound-of-sorting/main_babel.js (limited to 'sound-of-sorting') 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 @@ + + + + + +Chrisoft::Sound of Sorting + + + + + +

+ +

+ Read Access:
+ Write Access: +

+ 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 ab?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=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+ih.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=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;LL;--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;i0) + { + 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=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;i0)--le; + else + { + if(!--n)break; + h.swap(0,n); + h.mark(n,1); + if(n+10)++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=h.count)continue; + h.mark(ps[i],3); + } + for(let i=0;ii) + { + h.swap(L+i,L+j); + await this.wait(); + } + i+=c[Math.floor(h.get(L+i)/base)%Rdx]; + } + for(let i=0;ipm)return; + let s=L; + for(let i=0;i1) + 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;i0;--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 ab?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;iwindow.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;ke?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(!(yy)){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(!(ss)){C.next=15;break}return q.mark(z-1,2),q.mark(z,1),0>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),!(qthis.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=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;ye?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