Last week I wrote about Using a Timer in a React Component but only gave a simple example. This week I'm going to review some code with more complexity.
A question came up on Reddit recently where someone was having difficulty creating a visual bubble sort in React. The posted code has a few problems. Take a look to see if you can spot any.
Original Code
bubbleSort() { const arr = this.state.array; const n = arr.length; for (let i = n - 1; i > 0; i--) { for (let j = 0; j < i; j++) { setTimeout(() => { if (arr[j] > arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; this.setState({ swaps: this.state.swaps + 1 }); } this.setState({ comparisons: this.state.comparisons + 1 }); }, i * 10); } } this.setState({ array: arr });}Code Review
Timers not cleaned up
Notice that each iteration of the inner loop registers a timer.
I'm not a fan of this, as I'll explain later. But aside from that, the timers are not cleaned up in the event the component is unmounted while some timers are still queued.
Your application will spit out a warning/error during development:
Warning: Can't perform a React state update on an unmounted component. This is a no-op, but it indicates a memory leak in your application. To fix, cancel all subscriptions and asynchronous tasks in the componentWillUnmount method.
Although this appears to be benign in production for now. Still... better to be in the habit of cleaning up after yourself.
And, as I'll show later, we can use a single setInterval() call instead of O(n2) setTimeout() calls.
Comparisons in the wrong order
This one is tricky... I didn't notice it at first.
See how the outer loop is counting down from n - 1 using the variable i? Now see how the delay for the timeout is i * 10... Since i starts big and gets smaller, the timeout delay is going to start big and get smaller. That means the code inside the setTimeout is going to execute in a different order than the code outside of the setTimeout.
This is the biggest issue since it affects the correctness of the algorithm.
We could fix this by simply changing the timeout value to (n - i) * 10 so that the inner block executes in the correct order. But hold on because I'll show you some even better improvements.
In-place mutation of state
Bubble sort happens in place. i.e. It doesn't require any additional space because items are swapped within the input array.
React depends on state being immutable -- the changing of state is what triggers re-rendering. But the array reference itself doesn't change when its elements are altered. Because of this, the following setState() call does nothing.
bubbleSort() { const arr = this.state.array; // ... create timers to modify arr in place this.setState({ array: arr }); // <-- No effect}There's another reason why that setState() is bad. All the array modifications haven't even happened by the time this setState() executes!
That's right... all the array swaps are queued up in setTimeout() calls. So even if the array had been copied so as to change the reference in state, the setState() call would have happened before the actual array modifications.
Were it not for the state changing when swaps and comparisons increase, the render would happen with stale array data and there would be no re-renders.
Correct use of variable scopes
Fortunately, the code uses let (as opposed to var) in the for loops.
for (let i = n - 1; i > 0; i--) { for (let j = 0; j < i; j++) {By doing this, new scopes are correctly created for variables i and j.
Had the code used var instead, the sort would have failed even worse (Refer to Understanding JavaScript Closures in For Loops for an explanation).
Side effects
Side effects are generally bad. What is a side effect?
Well... functions have inputs (parameters passed into the function) and outputs (stuff returned from the function). A side effect is something the function does to modify state by some mechanism other than returning output.
Side effects generally make functions more complex, more difficult to reason about, and more difficult to test. In this case, the side effects are creating timers and calling setState().
Single Responsibility Principle
The last "code smell" I want to mention is the violation of the Single Responsibility Principle, which refers to a function doing too many different things.
There is no question that the bubbleSort function should be responsible for sorting an array. But it's questionable to also have it be responsible for timing and trying to coordinate screen updates.
Once again, more complexity means more difficult to reason about and to test.
Rewrite
I hope by now I've convinced you that we shouldn't be calling setTimeout() from within the bubble sort algorithm. But we're going to need it somewhere because the whole idea is to create a visualization of bubble sort in action.
Inversion of control
There's a cool concept called Inversion of Control that I learned about way back in University (but I don't get many opportunities to apply it). This is the perfect place to apply it!
Inversion of control refers to taking all the state and flow control (i.e. the for-loops) and extracting it out into a state object that gets passed into the function and also returned as output. Control is inverted meaning that the caller controls flow, not the callee.
As a byproduct, the new bubble sort function will only execute one iteration of the algorithm on each pass and the calling code will need to call the function several times until it is done.
We need to move the loop counters i and j into state, along with a boolean to indicate when the algorithm is done.
Let's redefine the component state as follows:
type State = { array: number[]; swaps: number; comparisons: number; i: number; j: number; done: boolean;};Initializing state
We need a way to initialize the bubble sort state before we start calling the sorting function. This function takes an array and generates the initial state -- I arrived at this by examining what happens at the beginning of the bubbleSort() function.
//bubbleSort() {// const arr = this.state.array;// const n = arr.length;// for (let i = n - 1; ...; ...) {// for (let j = 0; ...; ...) {// ...function bubbleSortInit(array: number[]): State { return { array, swaps: 0, comparisons: 0, i: array.length - 1, j: 0, done: false, };}Stepping through bubble sort
We need to manually perform the bounds checks that the for-loops were doing previously. We also need to manually increment/decrement the loop counters. Here is the code for a single iteration of bubble sort.
function bubbleSortStep(state: State): Partial<State> { let { array, swaps, comparisons, i, j } = state; if (i <= 0) { return { done: true }; } if (array[j] > array[j + 1]) { let temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; swaps++; } comparisons++; if (++j >= i) { i--; j = 0; } return { array, swaps, comparisons, i, j, };}Testing
Hey, now that we've eliminated all the side effects... we can easily add unit tests!
describe('bubbleSort', () => { const random = [ ...new Array(100) ] .map(_ => Math.random() * 100); const sorted = [ ...random ] .sort((a, b) => a - b); const cases = [ { input: [ 10, 20, 30, 40, 50, 60 ], expected: [ 10, 20, 30, 40, 50, 60 ] }, { input: [ 60, 50, 40, 30, 20, 10 ], expected: [ 10, 20, 30, 40, 50, 60 ] }, { input: [ 20, 60, 10, 40, 50, 30 ], expected: [ 10, 20, 30, 40, 50, 60 ] }, { input: random, expected: sorted }, ]; cases.forEach(({ input, expected }, i) => { it(`case ${i + 1}`, () => { let state = bubbleSortInit(input); while (!state.done) { state = { ...state, ...bubbleSortStep(state) }; } expect(state.array).toEqual(expected); }); });});src/VisualBubbleSort.test.ts bubbleSort √ case 1 (2ms) √ case 2 (1ms) √ case 3 (1ms) √ case 4 (15ms)Adding the timer
Our component, rather than the bubble sort algorithm, will be responsible for the timer. We're going to use setInterval() instead of many setTimeout()'s because we are using a fixed delay between steps and we only need to call it once (this also makes cleanup easier!)
type State = { array: number[]; swaps: number; comparisons: number; i: number; j: number; done: boolean; timer: NodeJS.Timeout;};Inside the component, we'll add the following code. Note, the TSX has a button to trigger the start of sorting.
handleClick = () => { // Initialize the bubble sort state and start our timer this.setState({ ...bubbleSortInit(this.props.array), timer: setInterval(() => this.handleTimer(), 250) });}handleTimer = () => { this.setState(oldState => { // Perform one iteration of the sort and stop the // timer if we finished the algorithm. const newState = bubbleSortStep(oldState) as State; if (newState.done) { clearInterval(oldState.timer!); } return newState; });}componentWillUnmount() { // Stop the timer if we get unmounted. // Note: harmless if timer isn't running / never ran clearInterval(this.state.timer!);}Visualizing bubble sort
