Visualization example showing sort function comparison Sort algorithm is dependent on factors such as data type size order meta charset utf 8 style body height 1000px font family monospace font size x small bigContainer text align center big width 100 height 100 canvas border 1px solid black td vertical align top td first child vertical align middle thead text align center style link href https code jquery com ui 1 10 4 themes ui lightness jquery ui css rel stylesheet script src https code jquery com jquery 1 10 2 js script script src https code jquery com ui 1 10 4 jquery ui js script script var SortVisualizer function canvas this ctx canvas getContext 2d SortVisualizer prototype get function id var v this num this num id this num id 0 if id swap v Math floor v 2 return v SortVisualizer prototype runSort function sortFn size type type type random size size 50 this steps var self this var ascendingValues function ii size return ii var descendingValues function ii size return size ii 1 var manyEqualValues function ii size return 1 Math floor ii 10 10 var equalValues function ii size return Math floor size 2 var totallyRandom function ii size return self rand size var slightlyRandom function ii size return Math min size 1 Math max 0 ii 1 self rand 3 var makeRandomArray function size valueFn swapIndexFn var array for var ii 0 ii size ii array push valueFn ii size if swapIndexFn for var ii 0 ii size ii var a swapIndexFn ii size var b swapIndexFn ii size var t array a array a array b array b t for var ii 0 ii size ii self addStep_ ii array ii start return array var types random valueFn ascendingValues swapFn totallyRandom similar valueFn ascendingValues swapFn slightlyRandom ascending valueFn ascendingValues descending valueFn descendingValues mostEqual valueFn manyEqualValues swapFn totallyRandom equal valueFn equalValues var t types type var array makeRandomArray size t valueFn t swapFn sortFn array this SortVisualizer prototype addStep_ function index value type this steps push index index value value type type SortVisualizer prototype cancelTask_ function if this requestId undefined console log request canceled cancelRequestAnimtionFrame this requestId cancelTimeout this requestId this requestId undefined SortVisualizer prototype queueTask_ function fn var self this var bk function self requestId undefined fn if this requestId undefined throw task already queued this requestId requestAnimationFrame bk this requestId setTimeout bk 1000 SortVisualizer prototype playback function fn var index 0 var self this var steps this steps var ctx this ctx var size 0 var maxValue 0 this num cycles 0 var totalCycles 0 var cycleCount 0 var cyclesPerFrame 10 var columnState var columnsModified var time 0 var timeToRestore 20 var requestId undefined ctx fillStyle black ctx fillRect 0 0 ctx canvas width ctx canvas height steps forEach function step switch step type case start size Math max size step index 1 maxValue Math max maxValue step value columnState step index index step index time 0 value step value state start break default self num step type 0 break var queueNextStep function self queueTask_ processStep var modifyColumn function step var state columnState step index state value step value if state state start state state cmp state state step type state time time timeToRestore return true return false var drawColumn function step color var width ctx canvas width size var height ctx canvas height step value maxValue var x width step index var y ctx canvas height height ctx fillStyle black ctx fillRect x 0 width ctx canvas height ctx fillStyle color ctx fillRect x y width height var restoreColumns function var checkTime time columnState forEach function state if state state start if state time checkTime state state start drawColumn state white Each function returns the number of cycles it takes TODO Seems like we could simulate cache times since we know which elements have been references at what time var stepFuncs start function step drawColumn step white return 0 cmp function step if modifyColumn step drawColumn step blue return 3 swap function step drawColumn step red modifyColumn step return 6 copy function step drawColumn step purple modifyColumn step return 4 set function step drawColumn step orange modifyColumn step return 2 var drawAllColumns function var index 0 var drawNextColumn function if index columnState length columnState index state start drawColumn columnState index rgb 0 255 0 restoreColumns self queueTask_ drawNextColumn time drawNextColumn var processStep function var done false while done if index steps length fn false drawAllColumns done true else var step steps index var typeFn stepFuncs step type if typeFn throw unknown step type self num step type self num step type self num step type 1 1 var cycles typeFn step totalCycles cycles cycleCount cycles self num cycles totalCycles if cycleCount cyclesPerFrame cycleCount cyclesPerFrame queueNextStep fn true done true time restoreColumns processStep SortVisualizer prototype destroy function this cancelTask_ SortVisualizer prototype rand function range return Math floor Math random range SortVisualizer prototype swap function array a b var temp array a array a array b array b temp this addStep_ a array a swap this addStep_ b array b swap SortVisualizer prototype copy function array src dst array dst array src this addStep_ dst array dst copy SortVisualizer prototype set function array ndx value array ndx value this addStep_ ndx value set SortVisualizer prototype cmp function array ndx value this addStep_ ndx array ndx cmp return array ndx value SortVisualizer prototype gt function array ndx value return this cmp array ndx value 0 SortVisualizer prototype lt function array ndx value return this cmp array ndx value 0 SortVisualizer prototype ge function array ndx value return this cmp array ndx value 0 SortVisualizer prototype le function array ndx value return this cmp array ndx value 0 SortVisualizer prototype eq function array ndx value return this cmp array ndx value 0 SortVisualizer prototype ne function array ndx value return this cmp array ndx value 0 script script var log function msg var console document getElementById console var div document createElement div div appendChild document createTextNode msg console appendChild div var quickSort function array sv var sort function start end var n end start if n 1 return var r start sv rand n sv swap array start r sv var k start for var i start 1 i end i if sv le array i array start sv swap array k i sv sv swap array start k sv sort start k sort k 1 end sort 0 array length var quickSortLR function array sv var sort function array start end if end start 1 return var pivotIndex start var pivot array pivotIndex var sp start 1 var ep end while ep sp while ep sp sv ge array ep pivot ep if ep sp break sv copy array ep pivotIndex pivotIndex ep while ep sp sv le array sp pivot sp if ep sp break sv copy array sp pivotIndex pivotIndex sp sv set array pivotIndex pivot sort array start pivotIndex 1 sort array pivotIndex 1 end sort array 0 array length 1 var quickSort3 function array sv var sort function a l r if r l return var i l 1 var j r var p l 1 var q r var v a r for while sv lt a i v while sv gt a j v if j l break if i j break sv swap a i j if sv eq a i v this compare is nearly free because the swap above just accessed these values if a i v p sv swap a p i if sv eq a j v if a j v q sv swap a j q sv swap a i r j i 1 i i 1 for var k l k p k j sv swap a k j for var k r 1 k q k i sv swap a i k sort a l j sort a i r sort array 0 array length 1 var mergeSort function array sv var n array length var scratch array slice var merge function l r m var i l var j m 1 if l r return while i m j r if sv lt array i array j sv set scratch i j m 1 array i i else sv set scratch i j m 1 array j j for i m i sv set scratch i j m 1 array i for j r j sv set scratch i j m 1 array j for var k l k r k sv set array k scratch k for var run 1 run n run 2 for var i 0 i n i 2 run merge i Math min i 2 run 1 n 1 Math min i run 1 n 1 var bubbleSort function array sv var n array length for var i 0 i n i var swapped false for var j n 1 j i 1 j if sv lt array j array j 1 sv swap array j j 1 swapped true if swapped break var selectionSort function array sv var n array length for var i 0 i n i var k i for var j i 1 j n j if sv lt array j array k k j sv swap array i k var insertionSort function array sv var n array length for var i 1 i n i var v array i var j 0 for j i j if sv gt array j v break for var k i k j k sv copy array k 1 k sv set array j v var shellSort function array sv var n array length https oeis org A102549 701 301 132 57 23 10 4 1 forEach function gap for var i gap i n i var v array i var j i for j gap j gap if sv le array j gap v break for var k i k j k gap sv copy array k gap k sv set array j v function var createCanvas function width height var canvas document createElement canvas canvas width width canvas height height return canvas var bigSv undefined dialog form dialog autoOpen false height 900 width 900 modal true close function bigSv destroy bigSv undefined var showSort function algo type var big document getElementById big var width Math max 300 body width 200 var height Math max 300 body height 200 big width width 50 big height height 60 if bigSv undefined throw visualization already in progress bigSv new SortVisualizer big bigSv runSort algo sortFn Math max 100 Math min 300 width type bigSv playback function dialog form dialog title algo name type dialog option width width dialog option height height dialog open var types random similar ascending descending mostEqual equal var algorithms name quicksort sortFn quickSort name quicksortLR sortFn quickSortLR name quicksort3 sortFn quickSort3 name merge sortFn mergeSort name bubblesort sortFn bubbleSort name selection sortFn selectionSort name insertion sortFn insertionSort name Shell sortFn shellSort var stats label num set id set label num cpy id copy label num cmp id cmp label num swp id swap label num cyc id cycles var tbody document getElementById t var thead document getElementById h types forEach function type var td document createElement td td appendChild document createTextNode type thead appendChild td algorithms forEach function algo var tr document createElement tr var td document createElement td var div document createElement div div appendChild document createTextNode algo name td appendChild div tr appendChild td types forEach function type var td document createElement td var canvas createCanvas 100 50 td appendChild canvas var addDivSpan function parent msg var div document createElement div div appendChild document createTextNode msg var span document createElement span div appendChild span parent appendChild div return span var statElems stats forEach function stat statElems push stat stat elem addDivSpan td stat label var sv new SortVisualizer canvas sv runSort algo sortFn 50 type sv playback function statElems forEach function s s elem innerText sv get s stat id td click function showSort algo type tr appendChild td tbody appendChild tr console log ready script table thead tr id h td td tr thead tbody id t tbody table pre id console pre div id dialog form title Sort div id bigContainer canvas id big canvas div div
ent createElement div div appendChild document createTextNode msg console appendChild div var quickSort function array sv var sort function start end var n end start if n 1 return var r start sv rand n sv swap array start r sv var k start for var i start 1 i end i if sv le array i array start sv swap array k i sv sv swap array start k sv sort start k sort k 1 end sort 0 array length var quickSortLR function array sv var sort function array start end if end start 1 return var pivotIndex start var pivot array pivotIndex var sp start 1 var ep end while ep sp while ep sp sv ge array ep pivot ep if ep sp break sv copy array ep pivotIndex pivotIndex ep while ep sp sv le array sp pivot sp if ep sp break sv copy array sp pivotIndex pivotIndex sp sv set array pivotIndex pivot sort array start pivotIndex 1 sort array pivotIndex 1 end sort array 0 array length 1 var quickSort3 function array sv var sort function a l r if r l return var i l 1 var j r var p l 1 var q r var v a r for while sv lt a i v while sv gt a j v if j l break if i j break sv swap a i j if sv eq a i v this compare is nearly free because the swap above just accessed these values if a i v p sv swap a p i if sv eq a j v if a j v q sv swap a j q sv swap a i r j i 1 i i 1 for var k l k p k j sv swap a k j for var k r 1 k q k i sv swap a i k sort a l j sort a i r sort array 0 array length 1 var mergeSort function array sv var n array length var scratch array slice var merge function l r m var i l var j m 1 if l r return while i m j r if sv lt array i array j sv set scratch i j m 1 array i i else sv set scratch i j m 1 array j j for i m i sv set scratch i j m 1 array i for j r j sv set scratch i j m 1 array j for var k l k r k sv set array k scratch k for var run 1 run n run 2 for var i 0 i n i 2 run merge i Math min i 2 run 1 n 1 Math min i run 1 n 1 var bubbleSort function array sv var n array length for var i 0 i n i var swapped false for var j n 1 j i 1 j if sv lt array j array j 1 sv swap array j j 1 swapped true if swapped break var selectionSort function array sv var n array length for var i 0 i n i var k i for var j i 1 j n j if sv lt array j array k k j sv swap array i k var insertionSort function array sv var n array length for var i 1 i n i var v array i var j 0 for j i j if sv gt array j v break for var k i k j k sv copy array k 1 k sv set array j v var shellSort function array sv var n array length https oeis org A102549 701 301 132 57 23 10 4 1 forEach function gap for var i gap i n i var v array i var j i for j gap j gap if sv le array j gap v break for var k i k j k gap sv copy array k gap k sv set array j v function var createCanvas function width height var canvas document createElement canvas canvas width width canvas height height return canvas var bigSv undefined dialog form dialog autoOpen false height 900 width 900 modal true close function bigSv destroy bigSv undefined var showSort function algo type var big document getElementById big var width Math max 300 body width 200 var height Math max 300 body height 200 big width width 50 big height height 60 if bigSv undefined throw visualization already in progress bigSv new SortVisualizer big bigSv runSort algo sortFn Math max 100 Math min 300 width type bigSv playback function dialog form dialog title algo name type dialog option width width dialog option height height dialog open var types random similar ascending descending mostEqual equal var algorithms name quicksort sortFn quickSort name quicksortLR sortFn quickSortLR name quicksort3 sortFn quickSort3 name merge sortFn mergeSort name bubblesort sortFn bubbleSort name selection sortFn selectionSort name insertion sortFn insertionSort name Shell sortFn shellSort var stats label num set id set label num cpy id copy label num cmp id cmp label num swp id swap label num cyc id cycles var tbody document getElementById t var thead document getElementById h types forEach function type var td document createElement td td appendChild document createTextNode type thead appendChild td algorithms forEach function algo var tr document createElement tr var td document createElement td var div document createElement div div appendChild document createTextNode algo name td appendChild div tr appendChild td types forEach function type var td document createElement td var canvas createCanvas 100 50 td appendChild canvas var addDivSpan function parent msg var div document createElement div div appendChild document createTextNode msg var span document createElement span div appendChild span parent appendChild div return span var statElems stats forEach function stat statElems push stat stat elem addDivSpan td stat label var sv new SortVisualizer canvas sv runSort algo sortFn 50 type sv playback function statElems forEach function s s elem innerText sv get s stat id td click function showSort algo type tr appendChild td tbody appendChild tr console log ready script table thead tr id h td td tr thead tbody id t tbody table pre id console pre div id dialog form title Sort div id bigContainer canvas id big canvas div div