Array sort animation v 0.1.2

array-sort-animation-v-0-1-2.markdown

Array sort animation v 0.1.2

My second attempt at solving this problem. Found some free time and had fun making this.

A Pen by Sean Esteva on CodePen.

License.

index.pug

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
    
    

script.babel

/**
 * 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

style.less

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;    
    }
  }  
}