Using nested setTimeout to create an animated selection sort

Question

I am working on a basic sorting visualizer with using only HTML, CSS, and JS, and I've run into a problem with the animation aspect. To initialize the array, I generate random numbers within some specified range and push them on to the array. Then based on the webpage dimensions, I create divs for each element and give each one height and width dimensions accordingly, and append each to my "bar-container" div currently in the dom.

function renderVisualizer() {
  var barContainer = document.getElementById("bar-container");

  //Empties bar-container div
  while (barContainer.hasChildNodes()) {
    barContainer.removeChild(barContainer.lastChild);
  }

  var heightMult = barContainer.offsetHeight / max_element;
  var temp = barContainer.offsetWidth / array.length;
  var barWidth = temp * 0.9;
  var margin = temp * 0.05;
  //Creating array element bars
  for (var i = 0; i < array.length; i++) {
    var arrayBar = document.createElement("div");
    arrayBar.className = "array-bar"
    if (barWidth > 30)
      arrayBar.textContent = array[i];
    //Style
    arrayBar.style.textAlign = "center";
    arrayBar.style.height = array[i] * heightMult + "px";
    arrayBar.style.width = barWidth;
    arrayBar.style.margin = margin;

    barContainer.appendChild(arrayBar);
  }
}

I wrote the following animated selection sort and it works well, but the only "animated" portion is in the outer for-loop, and I am not highlighting bars as I traverse through them.

function selectionSortAnimated() {
  var barContainer = document.getElementById("bar-container");
  var barArr = barContainer.childNodes;
  for (let i = 0; i < barArr.length - 1; i++) {
    let min_idx = i;
    let minNum = parseInt(barArr[i].textContent);
    for (let j = i + 1; j < barArr.length; j++) {
      let jNum = parseInt(barArr[j].textContent, 10);
      if (jNum < minNum) {
        min_idx = j;
        minNum = jNum;
      }
    }
    //setTimeout(() => {   
    barContainer.insertBefore(barArr[i], barArr[min_idx])
    barContainer.insertBefore(barArr[min_idx], barArr[i]);
    //}, i * 500);
  }
}

I am trying to use nested setTimeout calls to highlight each bar as I traverse through it, then swap the bars, but I'm running into an issue. I'm using idxContainer object to store my minimum index, but after each run of innerLoopHelper, it ends up being equal to i and thus there is no swap. I have been stuck here for a few hours and am utterly confused.

function selectionSortTest() {
  var barContainer = document.getElementById("bar-container");
  var barArr = barContainer.childNodes;
  outerLoopHelper(0, barArr, barContainer);
  console.log(array);
}

function outerLoopHelper(i, barArr, barContainer) {
  if (i < array.length - 1) {
    setTimeout(() => {
      var idxContainer = {
        idx: i
      };
      innerLoopHelper(i + 1, idxContainer, barArr);
      console.log(idxContainer);
      let minIdx = idxContainer.idx;
      let temp = array[minIdx];
      array[minIdx] = array[i];
      array[i] = temp;

      barContainer.insertBefore(barArr[i], barArr[minIdx])
      barContainer.insertBefore(barArr[minIdx], barArr[i]);
      //console.log("Swapping indices: " + i + " and " + minIdx);
      outerLoopHelper(++i, barArr, barContainer);
    }, 100);
  }
}

function innerLoopHelper(j, idxContainer, barArr) {
  if (j < array.length) {
    setTimeout(() => {
      if (j - 1 >= 0)
        barArr[j - 1].style.backgroundColor = "gray";
      barArr[j].style.backgroundColor = "red";
      if (array[j] < array[idxContainer.idx])
        idxContainer.idx = j;
      innerLoopHelper(++j, idxContainer, barArr);
    }, 100);
  }
}

I know this is a long post, but I just wanted to be as specific as possible. Thank you so much for reading, and any guidance will be appreciated!

you need a function wrapper to alias i, using closure to preserve its value at time of calling setTimeout instead of function execution time. lookup about using setTimeout in loops. — dandavis
– dandavis, Commented Aug 3, 2020 at 7:30
Sounds like you are trying to solve a CSS problem with JavaScript to me. — Adrian Brand
– Adrian Brand, Commented Aug 5, 2020 at 22:39
I'm not sure how I would animate divs moving around the screen with css though. @dandavis I don't fully understand your comment; can you please elaborate? I looked up the way setTimeout is used in loops and I was able to recreate the examples, but I can't find anything useful about nested setTimeouts — Big Boss
– Big Boss, Commented Aug 6, 2020 at 3:09

Kaiido · Accepted Answer · 2020-08-11 02:56:03Z

Convert your sorting function to a generator function*, this way, you can yield it the time you update your rendering:

const sorter = selectionSortAnimated();
const array = Array.from( { length: 100 }, ()=> Math.round(Math.random()*50));
const max_element = 50;
renderVisualizer();
anim();

// The animation loop
// simply calls itself until our generator function is done
function anim() {
  if( !sorter.next().done ) {
    // schedules callback to before the next screen refresh
    // usually 60FPS, it may vary from one monitor to an other
    requestAnimationFrame( anim );
    // you could also very well use setTimeout( anim, t );
  }
}
// Converted to a generator function
function* selectionSortAnimated() {
  const barContainer = document.getElementById("bar-container");
  const barArr = barContainer.children;
  for (let i = 0; i < barArr.length - 1; i++) {
    let min_idx = i;
    let minNum = parseInt(barArr[i].textContent);
    for (let j = i + 1; j < barArr.length; j++) {
      let jNum = parseInt(barArr[j].textContent, 10);
      if (jNum < minNum) {
        barArr[min_idx].classList.remove( 'selected' );
        min_idx = j;
        minNum = jNum;
        barArr[min_idx].classList.add( 'selected' );
      }
      // highlight
      barArr[j].classList.add( 'checking' );
      yield; // tell the outer world we are paused
      // once we start again
      barArr[j].classList.remove( 'checking' );
    }
    barArr[min_idx].classList.remove( 'selected' );
    barContainer.insertBefore(barArr[i], barArr[min_idx])
    barContainer.insertBefore(barArr[min_idx], barArr[i]);
    // pause here too?
    yield;
  }
}
// same as OP
function renderVisualizer() {
  const barContainer = document.getElementById("bar-container");

  //Empties bar-container div
  while (barContainer.hasChildNodes()) {
    barContainer.removeChild(barContainer.lastChild);
  }

  var heightMult = barContainer.offsetHeight / max_element;
  var temp = barContainer.offsetWidth / array.length;
  var barWidth = temp * 0.9;
  var margin = temp * 0.05;
  //Creating array element bars
  for (var i = 0; i < array.length; i++) {
    var arrayBar = document.createElement("div");
    arrayBar.className = "array-bar"
    if (barWidth > 30)
      arrayBar.textContent = array[i];
    //Style
    arrayBar.style.textAlign = "center";
    arrayBar.style.height = array[i] * heightMult + "px";
    arrayBar.style.width = barWidth;
    arrayBar.style.margin = margin;

    barContainer.appendChild(arrayBar);
  }
}

#bar-container {
  height: 250px;
  white-space: nowrap;
  width: 3500px;
}
.array-bar {
  border: 1px solid;
  width: 30px;
  display: inline-block;
  background-color: #00000022;
}
.checking {
  background-color: green;
}
.selected, .checking.selected {
  background-color: red;
}

<div id="bar-container"></div>

Thank you so much for introducing the concept of "generator functions," I've used it along with setTimeout to create a generic sort function which accepts a generator function as a parameter.

dave · Accepted Answer · 2020-08-11 01:58:58Z

So I thought about this, and it's a little tricky, what I would do is just store the indexes of each swap as you do the sort, and then do all of the animation seperately, something like this:

// how many elements we want to sort
const SIZE = 24;

// helper function to get a random number
function getRandomInt() {
  return Math.floor(Math.random() * Math.floor(100));
}

// this will hold all of the swaps of the sort.
let steps = [];

// the data we are going to sort
let data = new Array(SIZE).fill(null).map(getRandomInt);
// and a copy that we'll use for animating, this will simplify
// things since we can just run the sort to get the steps and
// not have to worry about timing yet.
let copy = [...data];

let selectionSort = (arr) => {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        let min = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min !== i) {
            let tmp = arr[i];
            // save the indexes to swap
            steps.push({i1: i, i2: min});
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    return arr;
}

// sort the data
selectionSort(data);

const container = document.getElementById('container');
let render = (data) => {
    // initial render...
    data.forEach((el, index) => {
        const div = document.createElement('div');
        div.classList.add('item');
        div.id=`i${index}`;
        div.style.left = `${2 + (index * 4)}%`;
        div.style.top = `${(98 - (el * .8))}%`
        div.style.height = `${el * .8}%`
        container.appendChild(div);
    });
}

render(copy);

let el1, el2;
const interval = setInterval(() => {
    // get the next step
    const {i1, i2} = steps.shift();
    if (el1) el1.classList.remove('active');
    if (el2) el2.classList.remove('active');
    el1 = document.getElementById(`i${i1}`);
    el2 = document.getElementById(`i${i2}`);
    el1.classList.add('active');
    el2.classList.add('active');
    [el1.id, el2.id] = [el2.id, el1.id];
    [el1.style.left, el2.style.left] = [el2.style.left, el1.style.left]
    if (!steps.length) {
        clearInterval(interval);
        document.querySelectorAll('.item').forEach((el) => el.classList.add('active'));
    }
}, 1000);

#container {
    border: solid 1px black;
    box-sizing: border-box;
    padding: 20px;
    height: 200px;
    width: 100%;
    background: #EEE;
    position: relative;
}

#container .item {
    position: absolute;
    display: inline-block;
    padding: 0;
    margin: 0;
    width: 3%;
    height: 80%;
    background: #cafdac;
    border: solid 1px black;
    transition: 1s;
}

#container .item.active {
    background: green;
}

<div id="container"></div>

Collectives™ on Stack Overflow

Using nested setTimeout to create an animated selection sort

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related