Skip to content

Blog

Jump to bottom
Drew Thurman edited this page Dec 13, 2023 · 5 revisions

-11/23

The first iteration of the actual visualizer for bubble sort is tentatively done. Inside are some details about my thought processes while building, notes on drawbacks or roadblocks, and how I decided to solve these issues.

  • I started by creating functions to generate a list of random numbers, and employed useState to store the generated "sortingArray", and mapped over these values in the jsx to create a column for each.

    • columns code: 
          function ArrayElementNode({ color, label }: { color: string; label: string }) {
      return (
        <div className={`flex h-full w-3 justify-center items-end text-xs ${color}`}>
          <div className="translate-y-6 -rotate-45 text-white">{label}</div>
        </div>
      );
    }

    <div className="flex gap-4 h-1/2 w-full justify-center items-end">
      {sortingArray.map((value: number, idx: number, arr: number[]) => {
        return (
          <div className="array-element-node" key={value} style={{ height: value }}>
            <ArrayElementNode
              key={idx}
              label={arr.length < 30 ? ${value} : ""}
              color={"bg-blue"}
            />
          </div>
        );
      })}
    </div>

    • While testing I noticed column labels tend to overlap and look ugly when the list is above 30-40 elements.

  • With the ability to create a random array of numbers and render them on the screen, the next step would be to implement a version of bubble sort that keeps track of the steps it took to sort the array. For this step I modified traditional bubbleSort to create an auxiliary array called animationFrames. The plan is to push a copy of the sortingArray to animationFrames on each iteration of the inner loop. This would give me a snapshot of the sortingArray's state after every comparison. I could use these captured array states to illustrate the steps taken to sort the input array.

    • bubbleSort code: 
        generateBubbleSortAnimations(arr: number[]): number[][] {
    const arrayCopy = [...arr];
    const bubbleSortAnimations = []
    let swapped = true;

    while (swapped) {
      swapped = false;
      for (let i = 0; i < arrayCopy.length - 1; i++) {
        if (arrayCopy[i] > arrayCopy[i + 1]) {
          bubbleSortAnimations.push([i, i+1])
          const temp = arrayCopy[i];
          arrayCopy[i] = arrayCopy[i + 1];
          arrayCopy[i + 1] = temp;
          swapped = true;
        }
      }
    } ;

    return bubbleSortAnimations;
  };

    • I realized that this was wasteful, as it would produce an unused animation frame when the numbers being compared are already in order. Also, since I'm only concerned with the positions being changed, I modified it to store the two positions being swapped only when I've made a change.

  • The next order of business would be to create a function, handleFrame, which would handle a single animation frame by modifying the currently rendered array elements to reflect the new state of the array. I imagined 3 visual indicators to guide the user through the steps. First, I would change the colors of the elements to be swapped. Next I would swap the style properties and labels of the two elements, and finally I would return them to the default color. I used regular DOM manipulation to achieve all of this, like so:

    • handleFrame code: 
      ```typescript
const handleFrame = (frameNumber: number, col1: any, col2: any) => {
  let c1h = col1.style.height;
  let c2h = col2.style.height;
  let el1 = col1.firstChild;
  let el2 = col2.firstChild;
  let text = el1.firstChild.innerText;

  if (frameNumber % 3 === 1) {
    el1.style.backgroundColor = "red";
    el2.style.backgroundColor = "purple";
  } else if (frameNumber % 3 === 2) {
    el1.style.backgroundColor = "purple";
    el2.style.backgroundColor = "red";
    el1.firstChild.innerText = el2.firstChild.innerText;
    el2.firstChild.innerText = text;
    col1.style.height = c2h;
    col2.style.height = c1h;
  } else {
    el1.style.backgroundColor = "blue";
    el2.style.backgroundColor = "blue";
  }

  };

  ```

  • With these steps completed I could begin to put everything together. My plan was to iterate over the animation frames, creating a set of nested timeouts. The higher order timeout would be responsible for grabbing the proper array columns and creating 3 staggered calls to the handleFrame function described above. To start and stop the animations I decided to employ useEffect's dependancy array in conjunction with a slice of local state called "sortingInProgress", which the "Sort" button would manipulate. It's not the most beautiful code, but this is what I came up with for the first iteration:

    • useEffect code: 
        useEffect(() => {
    if (!sortingInProgress) return;
    const animationFrames = generateBubbleSortAnimations(sortingArray);
    for (let i = 0; i < animationFrames.length; i++) {
      setTimeout(() => {
        const arrayElements = document.querySelectorAll(
          ".array-element-node"
        );
        const [pos1, pos2] = animationFrames[i];
        const col1 = arrayElements[pos1];
        const col2 = arrayElements[pos2];
        for (let idx = 1; idx <= 3; idx++) {
          setTimeout(() => {
            handleFrame(idx, col1, col2);
          }, idx * 15);
        }
      }, i * 45);
    }
  }, [sortingInProgress]);
  ```
</details>

  • Lastly, I made a few simple buttons. One to start the sorting visualization, and one to create / render a new list of values. So. The creation is complete. It works but, even aside from sloppy first-attempt code, there are drawbacks and things that I would like to refactor. Here's what I'd like to address in the next iteration:

    1. The visualization is kind of jarring. It gets the point across, but it's not pretty.
      • a. the columns don't move horizontally, they just swap sizes.
      • b. since there are no transitions the changes happen instantly.
      • c. faster animation speeds make this look like a blur of colors, then it's done - not the desired effect
    2. Once animations start, they cannot be stopped.
      • b. it is not possible to pause, rewind or reset back to the original list order.
      • a. if a new list is generated during animation, the column values update but the animations continue.
The second iteration of the bubble sort visualizer is mostly complete. In this iteration of the component I wanted to improve the animation of array columns as they were being sorted. I also wanted to address the issues I've found with the architecture, noted at the end of the previous post. Inside you'll find some details about the process.

Problem 1 - The visualization is jarring. It gets the point across, but it's not pretty.

  • The colors and sizes change in 3 sequential steps for each swap, but each step happens instantly... and there's no movement. This is because I'm using regular dom manipulation without any transitions to "animate" the swaps. It's one thing to instantly change two columns' sizes and colors, implying we've made a swap - but I want the columns to actually trade places in front of the user. I needed to rethink my methodology for making a swap. Here are the changes I decided to make:

    • the plan:

      1. Create a function that will literally swap two elements, instead of updating the columns' styles using vanilla dom manipulation.

      2. Refactor the single column component to be motion.divs inside of a LayoutGroup.

      3. Add a key to each column so framer-motion can keep track of its position.

      4. Swap elements in arrayValues and update columns using the new values.

      5. Framer-motion will handle the columns' animation/movement inside the LayoutGroup.

        • This works because: - React's diffing algorithm recognizes that 'columns' still has all the same elements, just in different positions, so it does not call createElement. Then, because they're not rebuilt, framer-motion will recognize the elements in the LayoutGroup are no longer in the correct places. - Finally framer-motion will animate/translateX the columns to their proper new positions in the rendered layout, effectively illustrating the swap.
  • the code: 
    const SingleArrayColumn = ({ key, value, speed }: SingleColumnProps) => {
  return (
    <motion.div
      key={key}
      layout
      className={`text-center min-w-[30px]`}
      transition={{ duration: speed, type: "spring" }}
    >
      <motion.div layout className="text-emerald-400" style={{ y: -20 }}>
        {value}
      </motion.div>
      <motion.div
        layout
        className="bg-violet-600"
        style={{
          height: `${value}px`,
        }}
      />
    </motion.div>
  );
};
    const createColumns = (array: { id: number, value: number }[]) => {
  return array.map((col) => (
    <SingleArrayColumn
      key={col.id}
      value={col.value}
      speed={ANIMATION_SPEED}
    />
  ));
};

const swapColumns = (...pos: number[]) => {
  let [a, b] = pos;
  [arrayValues[a], arrayValues[b]] = [arrayValues[b], arrayValues[a]];
  setColumns(createColumns(arrayValues));
};

Problem 2 - Once animations start, they cannot be stopped.

  • This is because all of the timeouts are placed onto the message queue synchronously. So even after the array values are changed, or sortingInProgress is toggled to false, handleFrame continues to be called as the timeouts resolve. My first response was to store each timeout id as it was being created in a ref, then clear them using a loop if the "cancel" button was clicked, but I was unsuccessful.

  • I decide to look at this from a different angle and try a recursive approach. Here's what I came up with.

    • the plan:

      1. use useRef to store:

        • animationFramesRef: the array of animation steps taken
        • timeoutRef: the ID of the current pending setTimeout

      2. use useState to store:

        • arrayValues: the list values to be mapped and sorted
        • columns: html elements created by mapping over arrayValues
        • sortingInProgress: used to toggle sorting on or off

      3. create a useEffect that will:

        • call a recursive function, "animateFrames", if sortingInProgress is true
        • return a cleanup function calls clearTimeout on timeoutRef

      4. animateFrames will:

        • create a new timeout whose callback will:
          • remove one frame from the animationFramesRef
          • call a helper function, "swapColumns", passing the removed animation frame
        • update timeoutRef with the new ID

      5. swapColumns will:

        • use the animation frame to swap the elements of "arrayValues"
        • call setArrayValues with the newly mutated array triggering a rerender, and starting the process over
  • the code: 
    useEffect(() => {
  if (!sortingInProgress) return;
  if (!animationFramesRef.current.length)
    animationFramesRef.current = sortingAlgos["bubbleSort"](arrayValues);
  animateFrames();
  return () => clearTimeout(timeoutRef.current);
}, [arrayValues, columns, sortingInProgress]);

const animateFrames = () => {
  timeoutRef.current = setTimeout(() => {
    if (animationFramesRef.current.length)
      swapColumns(...animationFramesRef.current.pop());
  }, ANIMATION_SPEED * 1000);
};

const swapColumns = (...pos: number[]) => {
  let [a, b] = pos;
  [arrayValues[a], arrayValues[b]] = [arrayValues[b], arrayValues[a]];
  setColumns(createColumns(arrayValues));
};

  • Users can pause or continue sorting at will, they can reset the columns back to their original positions to watch the same list being sorted again, and if the user generates a new array during sorting then the animations stop automatically. Additionally I feel like this code is quite a bit cleaner so I'm happy with the results, for now.

  • The next improvements I'd like to make here would be adding << and >> while sorting is paused. These buttons would "step" through the sorting operations 1 frame at a time.

    • Clone this wiki locally