ContextQMD
Back to Freecodecamp

Build a Sorting Visualizer

curriculum/challenges/english/blocks/lab-sorting-visualizer/6716249b5405164036fd0b0d.md

latest18.3 KB
Original Source

--description--

The Bubble Sort algorithm sorts a sequence of integers by comparing couples of adjacent elements starting from the beginning of the sequence. If the first element is greater than the second one, it swaps them. Then, it proceeds with the following couple. When the last element of the sequence is reached, it starts a new cycle from the beginning of the sequence, and repeats the process until the elements are sorted. The algorithm stops after one cycle completes with no swaps.

For this lab, you have been provided with all the HTML and CSS. You will use JavaScript to complete the Bubble Sort Visualizer so that it visualizes each step needed by the Bubble Sort algorithm to sort an array of five integers.

Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.

User Stories:

  1. You should have a function named generateElement that returns a random integer between 1 and 100, inclusive.
  2. You should have a function named generateArray that uses the generateElement function to return an array containing five random integers.
  3. You should have a function named generateContainer that creates and returns an empty div element.
  4. You should have a function named fillArrContainer that takes an HTML element as the first argument and an array as the second argument.
  5. The fillArrContainer should take an element as its first parameter and an array of integers as its second parameter, then populate the element with five span elements, with each span showing one of the integers from the array.
  6. You should have a function named isOrdered that takes two integers and returns a boolean indicating if the first integer is less than or equal to the second.
  7. You should have a function named swapElements that takes an array of integers and a numeric index.
  8. The swapElements function should modify the array in place by swapping the element at the passed index and the following element if isOrdered returns false.
  9. You should have a function named highlightCurrentEls that takes an HTML element and a numeric index.
  10. The highlightCurrentEls function should set the border of the given element's child at the given index, and the child immediately after the index, to have a dashed style, a red color, and a width of your choice.
  11. When you click #generate-btn you should use the fillArrContainer function to fill #starting-array with five span elements, each with a random number as its text. If present, other elements should be removed from #array-container.
  12. You should implement the Bubble Sort algorithm so that after you click #sort-btn, #array-container contains a div element for each of the steps required by the Bubble Sort algorithm to sort the starting array, including the div representing the starting array and a div representing the sorted array. The functions you have created so far can be useful here.
  13. Each div should contain five span elements, representing the array in its current state of being sorted.
  14. After you click #sort-btn, #starting-array should represent the starting step with the initial array and the first two integers highlighted.
  15. For each sorting step, you should use highlightCurrentEls to highlight the two numbers that are being compared, and swap them in the next step by using swapElements.

--hints--

You should have a function named generateElement.

js
assert.isFunction(generateElement);

Your generateElement function should return a random integer between 1 and 100 inclusive.

js
const randomMocker = new __helpers.RandomMocker();
randomMocker.mock();
try {    
    assert.strictEqual(generateElement(), 26);
    assert.strictEqual(generateElement(), 9);
} finally {
    randomMocker.restore();
}

You should have a function named generateArray.

js
assert.isFunction(generateArray)

Your generateArray function should make use of the generateElement function.

js
let flag = false;
const temp = generateElement;
generateElement = () => flag = true;
try {
    generateArray();
    assert.isTrue(flag);
} finally {
    generateElement = temp;
}

Your generateArray function should return an array containing five random integers between 1 and 100.

js
const randomMocker = new __helpers.RandomMocker();
randomMocker.mock();
try {
    assert.deepEqual(generateArray(), [26, 9, 58, 23, 38])
} finally {
    randomMocker.restore();
}

You should have a function named generateContainer.

js
assert.isFunction(generateContainer);

Your generateContainer function should return an empty div element.

js
const div = generateContainer();
assert.equal(div.tagName, "DIV");
assert.isEmpty(div.children);

You should have a function named fillArrContainer.

js
assert.isFunction(fillArrContainer);

Your fillArrContainer() should take an element as its first parameter and an array of integers as its second parameter, then populate the element with five span elements, with each span showing one of the integers from the array.

js
const testDiv = document.createElement("div");
const testArr = [15, 98, 17, 5, 63]
fillArrContainer(testDiv, testArr);
const children = testDiv.children;
assert.lengthOf(children, 5);
Array.from(children).forEach((el, i) => {
    assert.equal(el.tagName, "SPAN");
    assert.equal(el.innerText.trim(), testArr[i])
})

You should have a function named isOrdered.

js
assert.isFunction(isOrdered);

Your isOrdered function should take two integers and should return a boolean indicating if the first integer is less than or equal to the second.

js
assert.lengthOf(isOrdered, 2);
assert.isTrue(isOrdered(2, 60));
assert.isFalse(isOrdered(10, 3));
assert.isTrue(isOrdered(5, 5));

You should have a function named swapElements.

js
assert.isFunction(swapElements);

Your swapElements function take an array of integers and a numeric index as arguments. It should modify the array passed in place by swapping the element at the given index and the following element if the first element is greater than the second.

js
const testArr = [22, 4, 87, 47, 33];
swapElements(testArr, 0);
assert.deepEqual(testArr, [4, 22, 87, 47, 33]);
swapElements(testArr, 1);
assert.deepEqual(testArr, [4, 22, 87, 47, 33]);
swapElements(testArr, 2);
assert.deepEqual(testArr, [4, 22, 47, 87, 33]);
swapElements(testArr, 3);
assert.deepEqual(testArr, [4, 22, 47, 33, 87]);

You should have a function named highlightCurrentEls.

js
assert.isFunction(highlightCurrentEls);

Your highlightCurrentEls function should give the descendants of the specified element, located at the given index and the next index, a border that is dashed, red, and set to a width of your choice.

js
const testDiv = document.createElement("div");
document.querySelector("body").appendChild(testDiv)
for (let i = 0; i < 5; i++) {
    testDiv.appendChild(document.createElement("span"));
}
const redBorderRegex = /dashed (rgb\(255,\s*0,\s*0\)|#FF0000|#F00|hsl\(0,\s*100%,\s*50%\))/;
const revertBorder = () => {
    for (const el of children) {
        el.style.border = "revert";
    }
}
const children = testDiv.children;

for (let i = 0; i < 3; i++) {
    highlightCurrentEls(testDiv, i);
    for (let j = 0; j < 5; j++) {
        let b = getComputedStyle(children[j]).border;
        if (j == i || j == i + 1) {            
            assert.match(b, redBorderRegex);
            assert.isAbove(parseFloat(b), 0);
        } else {
            assert.notMatch(b, redBorderRegex);
        }
    }
    revertBorder();
}
testDiv.remove();

When you click #generate-btn you should fill #starting-array with five span elements, each with a random number between 1 and 100 as its text.

js
const genBtn = document.querySelector("#generate-btn");
genBtn.click();
const children = document.querySelector("#starting-array").querySelectorAll("span");
assert.lengthOf(children, 5);
Array.from(children).forEach(el => {
    assert.equal(el.tagName, "SPAN");
    const num = Number(el.innerText.trim());
    assert.isAtMost(num, 100);
    assert.isAtLeast(num, 1);
})

When #starting-array already contains a generated array, or #array-container contains the sorted array, clicking the #generate-btn should remove other elements in the #array-container, leaving only #starting-array with newly generated numbers.

js
const genBtn = document.querySelector("#generate-btn");
const sortBtn = document.querySelector("#sort-btn");
genBtn.dispatchEvent(new Event("click"));

const prevNumbers = Array.from(document.querySelector("#starting-array").querySelectorAll("span")).map(el => Number(el.innerText.trim()));

sortBtn.dispatchEvent(new Event("click"));
genBtn.dispatchEvent(new Event("click"));

const container = document.querySelector("#array-container");
assert.lengthOf(container.children, 1);
const numbers = Array.from(document.querySelector("#starting-array").querySelectorAll("span")).map(el => Number(el.innerText.trim()));
assert.lengthOf(numbers, 5);
assert.isTrue(prevNumbers.some((num, index) => num !== numbers[index]))

After you click #sort-btn, #array-container should contain as many div elements as the steps required by the Bubble Sort algorithm to sort the starting array, including the div representing the starting array and a div representing the sorted array.

js
const genBtn = document.querySelector("#generate-btn");
const sortBtn = document.querySelector("#sort-btn");
// using randomMocker to be sure that the starting array requires 13 steps to be sorted
const randomMocker = new __helpers.RandomMocker();
randomMocker.mock();
try {    
    genBtn.dispatchEvent(new Event("click"));
    sortBtn.dispatchEvent(new Event("click"));
    const container = document.querySelector("#array-container");
    assert.lengthOf(container.children, 13)
    Array.from(container.children).forEach(el => {assert.equal(el.tagName, "DIV")})
} finally {
    randomMocker.restore();
}

After you click #sort-btn, each div within #array-container should contain five span, each with a number as its text, and arranged to represent the steps required by Bubble Sort algorithm to sort the starting array.

js
const finalArr = [9, 23, 26, 38, 58];
const arrays = [
    [26, 9, 58, 23, 38],
    [9, 26, 58, 23, 38],
    [9, 26, 58, 23, 38],
    [9, 26, 23, 58, 38],
    [9, 26, 23, 38, 58],
    [9, 26, 23, 38, 58],
    finalArr,
    finalArr,
    finalArr,
    finalArr,
    finalArr,
    finalArr,
    finalArr
]
const genBtn = document.querySelector("#generate-btn");
const sortBtn = document.querySelector("#sort-btn");
const randomMocker = new __helpers.RandomMocker();
randomMocker.mock();
try {    
    genBtn.dispatchEvent(new Event("click"));
    sortBtn.dispatchEvent(new Event("click"));
    const container = document.querySelector("#array-container");
    assert.isNotEmpty(container.children);
    Array.from(container.children).forEach((el, i) => {
        Array.from(el.children).forEach((j, k) => {
            assert.strictEqual(Number(j.innerText.trim()), arrays[i][k])
        })
    })
} finally {
    randomMocker.restore();
}

When you click the #sort-btn, you should make use of the highlightCurrentEls function to highlight the elements being compared in each step.

js
const genBtn = document.querySelector("#generate-btn");
const sortBtn = document.querySelector("#sort-btn");
let flag = false;
const temp = highlightCurrentEls;
highlightCurrentEls = () => flag = true;
try {
    genBtn.dispatchEvent(new Event("click"));
    sortBtn.dispatchEvent(new Event("click"));
    assert.isTrue(flag);
} finally {
    highlightCurrentEls = temp;
}

After you click #sort-btn, #starting-array should represent the starting step with the initial array and the first two integers highlighted using highlightCurrentEls.

js
const genBtn = document.querySelector("#generate-btn");
const sortBtn = document.querySelector("#sort-btn");   
genBtn.dispatchEvent(new Event("click"));
sortBtn.dispatchEvent(new Event("click"));
const firstContainer = document.querySelector("#starting-array");
const children = firstContainer.children
const redBorderRegex = /dashed (rgb\(255,\s*0,\s*0\)|#FF0000|hsl\(0,\s*100%,\s*50%\))/;
assert.match(getComputedStyle(children[0]).border, redBorderRegex);
assert.match(getComputedStyle(children[1]).border, redBorderRegex);

--seed--

--seed-contents--

html
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Sorting Visualizer</title>
    <link rel="stylesheet" href="styles.css">
</head>

<body>
    <main>
        <div id="array-container">
            <div id="starting-array"></div>
        </div>
        <div id="btn-container">
            <button id="generate-btn" type="button">Generate Array</button>
            <button id="sort-btn" type="button">Sort Array</button>
        </div>
    </main>
    <script src="script.js"></script>
</body>

</html>
css
* {
    box-sizing: border-box;
}

main {
    height: 100vh;
    display: flex;
    justify-content: center;
    flex-direction: column;
    align-items: center;
}

#array-container {
    max-height: 95vh;
    display: flex;
    flex-direction: column;
    flex-wrap: wrap;
    gap: 2px;

}

#array-container>div {
    min-width: 8rem;
    height: 2rem;
    box-shadow: rgba(50, 50, 93, 0.25) 0px 2px 5px -1px, rgba(0, 0, 0, 0.3) 0px 1px 3px -1px;
    border-radius: 10px;
    margin-bottom: 0.2rem;
    border: 2px solid darkgray;
    display: flex;
    justify-content: space-evenly;
    align-items: center;
}

#starting-array {
    border: 4px solid darkblue !important;
}

#btn-container {
    display: flex;
    justify-content: space-around;
}

button {
    padding: 2px;
    margin: 5px;
}

span {
    border-radius: 2px;
    padding: 0.5px;
    margin: 0
}

@media (min-width: 430px) {
  #array-container>div {
    min-width: 12rem;    
  }
  span {
    padding: 1px;
    margin: 1px;
  }
}
js

--solutions--

html
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Sorting Visualizer</title>
    <link rel="stylesheet" href="styles.css">
</head>

<body>
    <main>
        <div id="array-container">
            <div id="starting-array"></div>
        </div>
        <div id="btn-container">
            <button id="generate-btn" type="button">Generate Array</button>
            <button id="sort-btn" type="button">Sort Array</button>
        </div>
    </main>
    <script src="script.js"></script>
</body>

</html>
css
* {
    box-sizing: border-box;
}

main {
    height: 100vh;
    display: flex;
    justify-content: center;
    flex-direction: column;
    align-items: center;
}

#array-container {
    max-height: 95vh;
    display: flex;
    flex-direction: column;
    flex-wrap: wrap;
    gap: 2px;

}

#array-container>div {
    min-width: 8rem;
    height: 2rem;
    box-shadow: rgba(50, 50, 93, 0.25) 0px 2px 5px -1px, rgba(0, 0, 0, 0.3) 0px 1px 3px -1px;
    border-radius: 10px;
    margin-bottom: 0.2rem;
    border: 2px solid darkgray;
    display: flex;
    justify-content: space-evenly;
    align-items: center;
}

#starting-array {
    border: 4px solid darkblue !important;
}

#btn-container {
    display: flex;
    justify-content: space-around;
}

button {
    padding: 2px;
    margin: 5px;
}

#sort-btn {
   display: none 
}

span {
    border-radius: 2px;
    padding: 0.5px;
    margin: 0
}

@media (min-width: 430px) {
  #array-container>div {
    min-width: 12rem;    
  }
  span {
    padding: 1px;
    margin: 1px;
  }
}
js
const arrayContainer = document.getElementById("array-container");
const generateArrayBtn = document.getElementById("generate-btn");
const sortArrayBtn = document.getElementById("sort-btn");
const arrayLength = 5;
const minVal = 1;
const maxVal = 100;
const isStart = () => arrayContainer.children.length === 1;
const clearArrayContainer = () => { arrayContainer.innerHTML = '<div id="starting-array"></div>' };
const showSortBtn = () => {sortArrayBtn.style.display = "inline-block"};
const hideSortBtn = () => {sortArrayBtn.style.display = "none"};
const generateElement = () => Math.floor(Math.random() * maxVal + minVal);
const generateArray = () => Array.from({ length: arrayLength }, generateElement);
const fillArrContainer = (container, arr) => {
    container.innerHTML = "";
    arr.forEach(i => {
        const el = document.createElement("span");
        el.innerText = i;
        el.id = `number-${i}`
        container.appendChild(el);
    })
}
const isOrdered = (el1, el2) => el1 <= el2;

const swapElements = (arr, n = 0) => {
    if (n < arr.length - 1 && !isOrdered(arr[n], arr[n + 1])) {
        const temp = arr[n];
        arr[n] = arr[n + 1];
        arr[n + 1] = temp;
    }
}
const getLastChildren = () => arrayContainer.lastElementChild;
const getLastArr = () => {
    const els = Array.from(getLastChildren().children);
    const arr = els.map(el => Number(el.id.replace("number-", "")));
    return arr;
}
const generateContainer = () => {
    const container = document.createElement("div");
    arrayContainer.appendChild(container);
    return container;
}
const highlightCurrentEls = (container, n = 0) => {
    const children = container.children;
    children[n].style.border = "2px dashed red";
    children[n + 1].style.border = "2px dashed red";
}

const highlightSorted = () => {
    getLastChildren().style.border = "4px solid green";
}

const bubbleSort = () => {
    let swapped = true;
    while (swapped) {
        const startingArr = getLastArr();
        startingArr.forEach((_, i) => {
            if (i + 1 < arrayLength) {
                highlightCurrentEls(getLastChildren(), i);
                const arr = getLastArr();
                swapElements(arr, i);
                fillArrContainer(generateContainer(), arr);
            }
        })
        const lastArr = getLastArr()
        if (startingArr.every((el, i) => el === lastArr[i])) swapped = false;
    }
}


generateArrayBtn.addEventListener("click", () => {
    if (!isStart()) {
        clearArrayContainer();
    }
    fillArrContainer(document.getElementById("starting-array"), generateArray());
    showSortBtn();
});

sortArrayBtn.addEventListener("click", () => {
    bubbleSort();
    highlightSorted();
    hideSortBtn();
})