I am trying to animate a quicksort visualiser just to understand the algorithm better. I have written an algorithm that works but I’m stuck on the animation bit. I followed a tutorial for mergesort that pushes all the values that is being compared into an array and I have done something similar. Currently my code colours the values that are being compared but does not rearrange the order of the values. I’m not sure how to go about swapping them into the correct order. Any help or guidance would be much appreciated!
Here is the algorithm in Javascript:
export function getQuickSortAnimations(array) {
const animations = [];
if (array.length <= 1) {
return array;
}
const pivot = array[array.length-1];
const leftArr = [];
const rightArr = [];
for (const el of array.slice(0, array.length-1)){
el <= pivot ? leftArr.push(el) : rightArr.push(el);
animations.push(["comparison1",el,pivot]); //To colour the compared values
animations.push(["comparison2",el,pivot]); //To take the colours off
}
let sortArray= [...getQuickSortAnimations(leftArr), pivot, ...getQuickSortAnimations(rightArr)];
return [animations, sortArray];
}
Here is the animation bit in React:
quickSort() {
const [animations, array] = getQuickSortAnimations(this.state.array);
for (let i = 0; i < animations.length; i++) {
const isColorChange = animations[i][0] === "comparison1" || animations[i][0] === "comparison2";
const arrayBars = document.getElementsByClassName('array-bar');
if(isColorChange === true) {
const [comparison, barOneIndex, barTwoIndex] = animations[i];
const color = (animations[i][0] === "comparison1") ? 'navy' : 'pink';
const barOneStyle = arrayBars[barOneIndex]?arrayBars[barOneIndex].style: {};
const barTwoStyle = arrayBars[barTwoIndex]?arrayBars[barTwoIndex].style:{};
setTimeout(() => {
barOneStyle.backgroundColor = color;
barTwoStyle.backgroundColor = color;
},i * ANIMATION_SPEED_MS);
}
else { //This is the section that I am not sure about
const [swap, barIndex, newHeight] = animations[i];
if (barIndex === -1) {
continue;
}
const barStyle = arrayBars[barIndex]?arrayBars[barIndex].style:{};
setTimeout(() => {
barStyle.height = `${newHeight}px`;
},i * ANIMATION_SPEED_MS);
}
}
}