1

I would like to show quicksort visually using vertical bars of different heights where the heights of the bars keeps on changing based on the algorithm.

If I use a quicksort function without setInterval, where only the final sorted result is displayed, it is working correctly. The version is the following.

function f(e) {
  initializeBlock()
  quicksort(0, n-1)
}

function quicksort(p, r){
  if (p < r){
    pivot = bars[r].offsetHeight
    var i = p - 1
    var j = p
    for (j = p; j < r; j++){
      if (bars[j].offsetHeight <= pivot) {
        i++
        temp = bars[i].offsetHeight
        bars[i].style.height = bars[j].offsetHeight + "px"
        bars[j].style.height = temp + "px"
      }
    }
    i++
    temp = bars[i].offsetHeight
    bars[i].style.height = bars[r].offsetHeight + "px"
    bars[r].style.height = temp + "px"
    quicksort(p, i-1)
    quicksort(i+1, r)
  }
}

call to the function be like :

goBtn.addEventListener('click', f)

Whereas if use setInterval with the quicksort function to actually display the quicksort happening, the result being displayed is incorrect i.e. the bars heights are only partially sorted. The version is the following.

function g(e){
  initializeBlock()
  quicksortWithInterval(0, n-1)
}

function quicksortWithInterval(p, r){
  if (p < r){
    pivot = bars[r].offsetHeight
    var i = p - 1
    var j = p
    var iId = setInterval(
      function() {
        if (bars[j].offsetHeight <= pivot) {
          i++
          temp = bars[i].offsetHeight
          bars[i].style.height = bars[j].offsetHeight + "px"
          bars[j].style.height = temp + "px"
        }
        if (++j == r) {
          clearInterval(iId)
          i++
          temp = bars[i].offsetHeight
          bars[i].style.height = bars[r].offsetHeight + "px"
          bars[r].style.height = temp + "px"
          quicksortWithInterval(p, i-1)
          quicksortWithInterval(i+1, r)
        }
    }, 1)
  }
}

call to the function be like :

goBtn.addEventListener('click', f)

I am not quite sure why is that because the recursive quicksort call are on independent sets? Please help clarify the issue here.

  • Your intervals are not waiting for the inner recursive to happen before triggering again. The best in your position would be to refactor it using a generator function. [See this Q/A.](https://stackoverflow.com/questions/46951400/using-canvas-to-animate-a-sorting-algorithm-in-js/46951855#46951855) for a similar case. – Kaiido Mar 04 '20 at 02:03

0 Answers0