My second attempt at solving this problem. Found some free time and had fun making this.
A Pen by Sean Esteva on CodePen.
My second attempt at solving this problem. Found some free time and had fun making this.
A Pen by Sean Esteva on CodePen.
div#app.s-app | |
section.s-ui | |
button( | |
name='btnPlay' | |
) Play | |
button( | |
name='btnPause' | |
) Pause | |
button( | |
name='btnPrevStep' | |
) Prev Step | |
button( | |
name='btnNextStep' | |
) Next Step | |
button( | |
name='btnReset' | |
) Reset | |
label | |
span Width of a column | |
select( | |
name='columnwidth' | |
) | |
option(value=40) 40 | |
option(value=30) 30 | |
option(value=20) 20 | |
option(value=15) 15 | |
option(value=10 selected) 10 | |
option(value=5) 5 | |
label | |
span Size of arrays | |
input( | |
type='number' | |
name='arraysize' | |
value=50 | |
maxlength=2 | |
min=4 | |
max=70 | |
) | |
label | |
span Steps per second | |
input( | |
type='number' | |
name='stepspersecond' | |
value=30 | |
maxlength=3 | |
min=1 | |
max=60 | |
) | |
label | |
input( | |
type='checkbox' | |
name='autoplay' | |
value=on | |
checked | |
) | |
. | |
Autoplay | |
label | |
input( | |
type='checkbox' | |
name='shownumbers' | |
value=on | |
) | |
. | |
Show numbers | |
/** | |
* Array sort animation. | |
* @version 0.1.2 | |
* @author Denis Khakimov <denisdude@gmail.com> | |
*/ | |
let NEXT_STEP = true | |
let PREV_STEP = false | |
let AUTOPLAY = true | |
let SHOW_NUMBERS = false | |
let COLUMN_WIDTH = 10 | |
let ARRAY_SIZE = 50 | |
let SPEED = 30 // steps per second | |
// init() -- begin | |
const init = (e) => { | |
let stepsBubble, stepsSelection, stepsInsertion, stepsMerge, stepsQuick | |
let A, B, C, D, E | |
let sA, sB, sC, sD, sE | |
const appContainer = document.getElementById('app') | |
const renderer = new Renderer(appContainer, 800, 800) | |
// INIT FUNCTIONS -- begin | |
let lastTime = Date.now() | |
let deltaTime = 0 | |
const tick = () => { | |
deltaTime = Date.now() - lastTime | |
if (deltaTime >= 1000 / SPEED) { | |
lastTime = Date.now() | |
render(deltaTime) | |
} | |
requestAnimationFrame(tick) | |
} | |
const reset = () => { | |
renderer.clear() | |
stepsBubble = new Steps('Bubble sort') | |
stepsSelection = new Steps('Selection sort') | |
stepsInsertion = new Steps('Insertion sort') | |
stepsMerge = new Steps('Merge sort') | |
stepsQuick = new Steps('Quick sort') | |
//let A = [4, 3, 7, 1, 5, 8, 2, 6, 1, 10, 4, 5] | |
A = Random1DArray(ARRAY_SIZE, 0, 100) | |
B = [...A] | |
C = [...A] | |
D = [...A] | |
E = [...A] | |
sA = BubbleSort(A, stepsBubble) | |
sB = SelectionSort(B, stepsSelection) | |
sC = InsertionSort(C, stepsInsertion) | |
sD = MergeSort(D, stepsMerge) | |
sE = QuickSort(E, stepsQuick) | |
NEXT_STEP = true | |
} | |
const render = (delta) => { | |
if (AUTOPLAY || NEXT_STEP) { | |
if (stepsBubble.hasNext()) | |
renderer.render( | |
stepsBubble.next(), 0, 0, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsSelection.hasNext()) | |
renderer.render( | |
stepsSelection.next(), 0, 150, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsInsertion.hasNext()) | |
renderer.render( | |
stepsInsertion.next(), 0, 300, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsMerge.hasNext()) | |
renderer.render( | |
stepsMerge.next(), 0, 450, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsQuick.hasNext()) | |
renderer.render( | |
stepsQuick.next(), 0, 600, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
NEXT_STEP = false | |
} | |
if (PREV_STEP) { | |
if (stepsBubble.hasPrev()) | |
renderer.render( | |
stepsBubble.prev(), 0, 0, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsSelection.hasPrev()) | |
renderer.render( | |
stepsSelection.prev(), 0, 150, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsInsertion.hasPrev()) | |
renderer.render( | |
stepsInsertion.prev(), 0, 300, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsMerge.hasPrev()) | |
renderer.render( | |
stepsMerge.prev(), 0, 450, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
if (stepsQuick.hasPrev()) | |
renderer.render( | |
stepsQuick.prev(), 0, 600, | |
SHOW_NUMBERS, COLUMN_WIDTH | |
) | |
PREV_STEP = false | |
} | |
} | |
const triggerEvent = (element, eventName) => { | |
const event = document.createEvent("HTMLEvents") | |
event.initEvent(eventName, false, true) | |
element.dispatchEvent(event) | |
} | |
// INIT FUNCTIONS -- end | |
// UI -- begin | |
const btnPlay = document.querySelector('button[name=btnPlay]') | |
btnPlay.addEventListener('click', (e) => { | |
autoplay.checked = true | |
triggerEvent(autoplay, 'change') | |
}) | |
const btnPause = document.querySelector('button[name=btnPause]') | |
btnPause.addEventListener('click', (e) => { | |
autoplay.checked = false | |
triggerEvent(autoplay, 'change') | |
}) | |
const btnNextStep = document.querySelector('button[name=btnNextStep]') | |
btnNextStep.addEventListener('click', (e) => { | |
NEXT_STEP = true | |
PREV_STEP = false | |
}) | |
const btnPrevStep = document.querySelector('button[name=btnPrevStep]') | |
btnPrevStep.addEventListener('click', (e) => { | |
PREV_STEP = true | |
NEXT_STEP = false | |
}) | |
const btnReset = document.querySelector('button[name=btnReset]') | |
btnReset.addEventListener('click', (e) => { | |
reset() | |
}) | |
const autoplay = document.querySelector('input[name=autoplay]') | |
autoplay.addEventListener('change', (e) => { | |
AUTOPLAY = e.target.checked | |
}) | |
const shownumbers = document.querySelector('input[name=shownumbers]') | |
shownumbers.addEventListener('change', (e) => { | |
SHOW_NUMBERS = e.target.checked | |
}) | |
const columnwidth = document.querySelector('select[name=columnwidth]') | |
columnwidth.addEventListener('change', (e) => { | |
COLUMN_WIDTH = parseInt(e.target.value) | |
reset() | |
}) | |
const arraysize = document.querySelector('input[name=arraysize]') | |
arraysize.addEventListener('change', (e) => { | |
ARRAY_SIZE = parseInt(e.target.value) | |
reset() | |
}) | |
const stepspersecond = document.querySelector('input[name=stepspersecond]') | |
stepspersecond.addEventListener('change', (e) => { | |
SPEED = parseInt(e.target.value) | |
}) | |
// UI -- end | |
reset() | |
tick() | |
} | |
// init() -- end | |
document.addEventListener('DOMContentLoaded', (e) => init(e)) | |
// STEPS -- begin | |
class Step { | |
constructor(stepArray, highlightArray) { | |
this.array = stepArray | |
this.highlight = highlightArray | |
this._parent = null | |
} | |
set parent(value) { | |
this._parent = value | |
} | |
/** | |
* @returns {Steps} | |
*/ | |
get parent() { | |
return this._parent | |
} | |
} | |
class Steps { | |
constructor(name) { | |
this.name = name | |
this.steps = [] | |
this.index = 0 | |
this.iterations = 0 | |
this.swaps = 0 | |
} | |
addIteration() { | |
this.iterations++ | |
} | |
addSwap() { | |
this.swaps++ | |
} | |
count() { | |
return this.steps.length | |
} | |
get length() { | |
return this.count() | |
} | |
/** | |
* | |
* @param {Step} step | |
*/ | |
addStep(step) { | |
this.steps.push(step) | |
step.parent = this | |
} | |
reset() { | |
this.index = 0 | |
} | |
peek() { | |
return this.steps[this.index] | |
} | |
next() { | |
this.index++ | |
return this.steps[this.index - 1] | |
} | |
hasNext() { | |
return this.count() > this.index | |
} | |
prev() { | |
this.index-- | |
return this.steps[this.index - 1] | |
} | |
hasPrev() { | |
return this.index > 1 | |
} | |
} | |
// STEPS -- end | |
// RENDERER -- begin | |
class Renderer { | |
/** | |
* @param {HTMLElement} canvasContainer | |
* @param {number} width | |
* @param {number} heigth | |
*/ | |
constructor(canvasContainer, width, height) { | |
this.width = width | |
this.height = height | |
this.canvasContainer = canvasContainer | |
this.canvas = document.createElement('canvas') | |
this.canvas.width = this.width | |
this.canvas.height = this.height | |
this.canvasContainer.prepend(this.canvas) | |
this.ctx = this.canvas.getContext('2d') | |
} | |
scale(v, min, max) { | |
return min + (max - min) * v | |
} | |
/** | |
* | |
* @param {Array} array | |
* @returns | |
*/ | |
max(array) { | |
return array.reduce((p, c) => { | |
return Math.max(p, c) | |
}, -Infinity) | |
} | |
clear() { | |
this.ctx.clearRect(0, 0, this.width, this.height) | |
} | |
/** | |
* Returns a key class for `index` | |
* @param {Step} step | |
* @param {number} index | |
*/ | |
getClass(step, index) { | |
const keys = Object.keys(step.highlight) | |
for (let key of keys) { | |
if (step.highlight[key].includes(index)) | |
return key | |
} | |
} | |
getTextColor(backgroundColor) { | |
if (backgroundColor.reduce((p, c) => p + c, 0) < 255) | |
return [255, 255, 255] | |
else | |
return [0, 0, 0] | |
} | |
/** | |
* | |
* @param {Step} step | |
*/ | |
render(step, shiftX = 0, shiftY = 0, showText = true, colWidth = 20) { | |
const boxWidth = colWidth | |
const minHeight = 20 | |
const maxHeight = 100 | |
const maxValue = this.max(step.array) | |
let sepWidth = 10 | |
if (boxWidth <= 10) sepWidth = 3 | |
const chartWidth = step.array.length * (boxWidth +sepWidth) | |
const minLeft = shiftX + (this.width - chartWidth) / 2 | |
const minTop = shiftY + 50 | |
this.ctx.clearRect( | |
minLeft, minTop, | |
chartWidth, maxHeight | |
) | |
const colorMap = { | |
default: [252, 219, 3], // default color | |
a: [0, 255, 0], // sorted | |
b: [3, 10, 230], // active | |
c: [255, 50, 50], // test | |
} | |
if (true) { | |
this.ctx.clearRect( | |
0, minTop - 30, | |
this.width, 30 | |
) | |
this.ctx.font = '14px Verdana' | |
this.ctx.textAlign = 'center' | |
this.ctx.fillStyle = `rgb(0, 0, 0)` | |
this.ctx.fillText( | |
`${step.parent.name}, step: ${step.parent.index}/${step.parent.count()}, swaps: ${step.parent.swaps}, iterations: ${step.parent.iterations}`, | |
minLeft + chartWidth / 2, | |
minTop - 15) | |
} | |
for (let i = 0; i < step.array.length; i++) { | |
const value = step.array[i] | |
const width = boxWidth | |
const height = this.scale( | |
value / maxValue, | |
minHeight, maxHeight | |
) | |
const x = minLeft + (i * (width + sepWidth)) | |
const y = minTop + maxHeight - height | |
const classKey = this.getClass(step, i) | |
const color = (classKey in step.highlight) | |
? colorMap[classKey] | |
: colorMap.default | |
this.ctx.fillStyle = `rgb(${color[0]}, ${color[1]}, ${color[2]})` | |
this.ctx.fillRect(x, y, width, height) | |
if (showText) { | |
const textColor = this.getTextColor(color) | |
this.ctx.font = '10px Verdana' | |
this.ctx.textAlign = 'center' | |
this.ctx.fillStyle = `rgb(${textColor[0]}, ${textColor[1]}, ${textColor[2]})` | |
this.ctx.fillText(value, x + width / 2, y + 15, 20) | |
} | |
} | |
} | |
} | |
// RENDERER -- end | |
// ALGO -- begin | |
function swap(A, i, j) { | |
const t = A[i] | |
A[i] = A[j] | |
A[j] = t | |
} | |
function range(from, to) { | |
const R = [] | |
for (let i = from; i <= to; i++) | |
R.push(i) | |
return R | |
} | |
function Random1DArray(len, min, max) { | |
const A = new Array(len) | |
for (let i = 0; i < len; i++) | |
A[i] = min + Math.floor(Math.random() * (max - min)) | |
return A | |
} | |
/** | |
* | |
* @param {Array} A | |
* @param {Steps} steps | |
* @returns | |
*/ | |
function BubbleSort(A, steps) { | |
steps.addStep(new Step( | |
[...A], {} | |
)) | |
for (let i = 0; i < A.length; i++) { | |
for (let j = 1; j < A.length - i; j++) { | |
if (A[j-1] > A[j]) { | |
swap(A, j, j-1) | |
steps.addSwap() | |
} | |
steps.addStep(new Step( | |
[...A], { | |
b: [j], | |
c: [j-1], | |
a: range(A.length - i, A.length - 1), | |
} | |
)) | |
steps.addIteration() | |
} | |
steps.addStep(new Step( | |
[...A], { | |
a: range(A.length - i - 1, A.length - 1), | |
} | |
)) | |
} | |
steps.addStep(new Step( | |
[...A], { | |
a: range(0, A.length - 1) | |
} | |
)) | |
return A | |
} | |
/** | |
* | |
* @param {Array} A | |
* @param {Steps} steps | |
* @returns | |
*/ | |
function SelectionSort(A, steps) { | |
steps.addStep(new Step( | |
[...A], {} | |
)) | |
for (let i = 0; i < A.length; i++) { | |
let min = i | |
for (let j = i + 1; j < A.length; j++) { | |
if (A[min] > A[j]) | |
min = j | |
steps.addStep(new Step( | |
[...A], { | |
b: [min], | |
c: [j], | |
a: range(0, i-1), | |
} | |
)) | |
steps.addIteration() | |
} | |
swap(A, min, i) | |
steps.addSwap() | |
steps.addStep(new Step( | |
[...A], { | |
b: [min], | |
a: range(0, i-1), | |
} | |
)) | |
} | |
steps.addStep(new Step( | |
[...A], { | |
a: range(0, A.length), | |
} | |
)) | |
return A | |
} | |
/** | |
* | |
* @param {Array} A | |
* @param {Steps} steps | |
* @returns | |
*/ | |
function InsertionSort(A, steps) { | |
steps.addStep(new Step( | |
[...A], {} | |
)) | |
let sorted = 0 | |
for (let i = 1; i < A.length; i++) { | |
let j = i | |
steps.addStep(new Step( | |
[...A], { | |
b: [j], | |
c: [i], | |
a: range(0, i-1), | |
} | |
)) | |
while (A[j] < A[j-1] && j > 0) { | |
swap(A, j--, j) | |
steps.addSwap() | |
steps.addStep(new Step( | |
[...A], { | |
b: [j+1], | |
c: [j], | |
a: range(0, i-1), | |
} | |
)) | |
steps.addIteration() | |
} | |
} | |
steps.addStep(new Step( | |
[...A], { | |
a: range(0, A.length), | |
} | |
)) | |
return A | |
} | |
/** | |
* | |
* @param {Array} A | |
* @param {Steps} steps | |
* @returns | |
*/ | |
function MergeSort(A, steps) { | |
steps.addStep(new Step( | |
[...A], {} | |
)) | |
const mergePart = (a, start, end) => { | |
const len = end - start | |
// base case | |
if (len <= 1) | |
return; | |
const mid = start + Math.floor(len / 2) | |
steps.addStep(new Step( | |
[...a], { | |
b: range(start, mid), | |
a: range(mid, end), | |
} | |
)) | |
mergePart(a, start, mid) | |
mergePart(a, mid, end) | |
merge(a, start, mid, end) | |
} | |
const merge = (a, start, mid, end) => { | |
const lenLeft = mid - start | |
const left = new Array(lenLeft) | |
for (let i = 0; i < lenLeft; i++) | |
left[i] = a[start + i] | |
const lenRight = end - mid | |
const right = new Array(lenRight) | |
for (let i = 0; i < lenRight; i++) | |
right[i] = a[mid + i] | |
let iL = 0 | |
let iR = 0 | |
let index = start | |
while (iL < lenLeft && iR < lenRight) { | |
steps.addStep(new Step( | |
[...a], { | |
b: [index], | |
} | |
)) | |
if (right[iR] > left[iL]) { | |
a[index++] = left[iL++] | |
} else { | |
a[index++] = right[iR++] | |
} | |
} | |
while (iL < lenLeft) { | |
a[index++] = left[iL++] | |
} | |
while (iR < lenRight) { | |
a[index++] = right[iR++] | |
} | |
steps.addStep(new Step( | |
[...a], { | |
c: range(start, end), | |
} | |
)) | |
} | |
mergePart(A, 0, A.length) | |
steps.addStep(new Step( | |
[...A], { | |
a: range(0, A.length), | |
} | |
)) | |
return A | |
} | |
/** | |
* | |
* @param {Array} A | |
* @param {Steps} steps | |
* @returns | |
*/ | |
function QuickSort(A, steps) { | |
steps.addStep(new Step( | |
[...A], {} | |
)) | |
const quick = (a, start, end) => { | |
// base case | |
if (start < end) { | |
const mid = partition(a, start, end) | |
steps.addStep(new Step( | |
[...A], { | |
b: range(start, mid), | |
a: range(mid, end), | |
} | |
)) | |
quick(a, start, mid - 1) | |
quick(a, mid + 1, end) | |
} | |
} | |
const partition = (a, start, end) => { | |
const pivot = end | |
let i = start - 1 | |
for (let j = start; j < pivot; j++) { | |
steps.addStep(new Step( | |
[...A], { | |
b: [pivot], | |
c: [j], | |
} | |
)) | |
if (a[pivot] > a[j]) { | |
swap(a, ++i, j) | |
steps.addSwap() | |
} | |
} | |
swap(a, ++i, pivot) | |
steps.addSwap() | |
return i | |
} | |
quick(A, 0, A.length - 1) | |
steps.addStep(new Step( | |
[...A], { | |
a: range(0, A.length), | |
} | |
)) | |
return A | |
} | |
// ALGO -- end |
html, body { | |
width: 100%; | |
height: 100%; | |
border: none; | |
margin: 0; | |
padding: 0; | |
font-size: 16px; | |
box-sizing: border-box; | |
} | |
body { | |
display: block; | |
position: relative; | |
background-color: rgb(145, 19, 190); | |
padding: 1rem; | |
font-family: Verdana, Geneva, Tahoma, sans-serif; | |
} | |
.s-app { | |
display: flex; | |
justify-content: flex-start; | |
align-items: flex-start; | |
margin: 0; | |
padding: 1rem; | |
width: calc(100vw - 2rem); | |
height: calc(100vh - 2rem); | |
background-color: rgb(25, 12, 85); | |
box-sizing: border-box; | |
} | |
.s-app canvas { | |
background: rgb(145, 19, 190); | |
background-color: rgb(255, 255, 255); | |
} | |
.s-ui { | |
display: block; | |
width: 100%; | |
max-width: 300px; | |
margin: 0; | |
padding: 0 1rem 1rem; | |
text-align: left; | |
input { | |
display: block; | |
width: 100%; | |
padding: .5rem 1rem; | |
font-size: 1.5rem; | |
box-sizing: border-box; | |
} | |
button { | |
font-size: 1.5rem; | |
cursor: pointer; | |
} | |
select { | |
font-size: 1.5rem; | |
} | |
button, | |
select { | |
display: inline-block; | |
width: 100%; | |
padding: .5rem 1rem; | |
} | |
button, | |
label { | |
margin: 0 auto 1rem; | |
} | |
label { | |
display: inline-block; | |
position: relative; | |
width: 100%; | |
font-size: 1.25rem; | |
font-weight: 400; | |
color: #fff; | |
> span { | |
display: block; | |
margin: 0 0 .5rem; | |
} | |
input[type=checkbox] { | |
position: relative; top: 2px; | |
display: inline-block; | |
width: 20px; height: 20px; | |
} | |
} | |
} | |