Insertion Sort & Shell Sort

_insertion-sort-shell-sort.markdown

Insertion Sort & Shell Sort

A Pen by bati11 on CodePen.

License.

index.html

<div>
  <p>input: [<span id="in"></span>]</p>
  <p>length: <span id="length">0</span></p>
</div>

<section>
  <h1>Insertion Sort</h1>
  <div class="values">
    <div>count: <span id="insertion-sort-counter">0</span>
    </div>
  </div>
  <div id="insertion-sort-result" class="result-box"></div>
</section>

<section>
  <h1>Shell Sort</h1>
  <div class="values">
    <div>gs: [<span id="gs"></span>]<br>count: <span id="shell-sort-counter">0</span></div>
  </div>
  <div id="shell-sort-result" class="result-box"></div>
</section>

script.js

let insertionSortCounter = 0
let shellSortCounter = 0
let as = []
let bs = []

async function main() {
  insertionSortCounter = 0
  shellSortCounter = 0
  as = [93,74,26,52,70,50,75,25,25,11,71,35,84,70,10,39,33,36,16,93,91,84,97]
  bs = [...as]
  const n = as.length
  document.querySelector("#in").innerHTML = as
  document.querySelector("#length").innerHTML = n

  console.log("START")

  const gs = createGS(n)
  document.querySelector("#gs").innerHTML = [...gs].reverse()

  const p1 = insertionSort(as, n, createRender(render, "insertion-sort"))
  const p2 = shellSort(bs, n, gs, createRender(render, "shell-sort"))

  Promise.all([p1, p2]).then((results) => {
    console.log("END")
  })
}

async function insertionSort(as, n, f = () => {}) {
  for (let i = 1; i < n; i++) {
    let j = i;
    for (; j > 0; j--) {
      if (as[j-1] > as[j]) {
        insertionSortCounter++
        await f(as, j-1, j, insertionSortCounter)
        let tmp = as[j-1]
        as[j-1] = as[j]
        as[j] = tmp
      } else {
        break
      }
    }
  }
  return f(as, -1, -1, insertionSortCounter)
}

function createGS(n) {
  const gs = []
  for (let h = 1; h <= n; h = 3 * h + 1) {
    gs.push(h)
  }
  console.log(`gs: ${gs}`)
  return gs
}

async function shellSort(bs, n, gs, f = () => {}) {
  for (let i = gs.length - 1; i >= 0; i--) {
    await _ssort(bs, n, gs[i], f)
  }
  return f(bs, -1, -1, shellSortCounter)
}

async function _ssort(bs, n, g, fn = () => {}) {
  for (let i = g; i < n; i++) {
    let v = bs[i]
    let j = i - g
    while (j >= 0 && bs[j] > v) {
      shellSortCounter++
      await fn(bs, j, i, shellSortCounter)
      bs[j+g] = bs[j]
      j = j - g
    }
    bs[j+g] = v
  }
}

/********************
 * render functions
 ********************/

let renderPromise = null

function createRender(f, sortType) {
  return async (as, t1, t2, count) => {
      const p = new Promise(resolve => {
        f(sortType, as, t1, t2, count)
        resolve()
      })
      if (renderPromise == null) {
        renderPromise = new Promise(r => setTimeout(r, 500))
          .then(() => {
            renderPromise = null
            return null
          })
          .then(p)
      } else {
        renderPromise.then(p)
      }
      return renderPromise
    }
}

function render(sortType, as, t1, t2, count) {
  const box = document.querySelector(`#${sortType}-result`)
  box.innerHTML = ''
  const bars = as.map((a, i) => {
    const bar = document.createElement("div")
    bar.style.width = "10px"
    bar.style.height = `${2 * a}px`
    if (i === t1) {
      bar.style.backgroundColor = "#f2dad9" // pink
    } else if (i === t2) {
      bar.style.backgroundColor = "#aca5ce" // purple
    } else {
      bar.style.backgroundColor = "#8ec6db" // blue
    }
    return bar
  })
  box.append(...bars)
  const counter = document.querySelector(`#${sortType}-counter`)
  counter.innerHTML = count
}

/********************
 * run
 ********************/
main()

style.scss

section {
  display: inline-block;
  padding: 0 24px;
  vertical-align: top;
  
  div.values {
    height: 2em;
    position: relative;
    
    div {
      height: auto;
      position: absolute;
      bottom: 0;
    }
  }
}
.result-box {
  padding-top: 20px;
  div {
    display: inline-block;
  }
}