DEV Community

Algorithms in JavaScript with visual examples.

Swastik Yadav on November 30, 2021

Hello Programmers, Most of us are scared of algorithms, and don't ever start to learn it. But we shouldn't be scared of it. An algorithm is just s...

Read full post

Jeff Chavez • Aug 25 '22

Wow. I'll learn this.

Swastik Yadav • Aug 26 '22

Glad that you liked it.

Sanzhar Danybayev • Dec 1 '21

You have an error in LSP value. It must be [0, 0, 0, 3, 5, 0] instead of [0, 0, 0, 1, 2, 0]

Sanzhar Danybayev • Dec 1 '21 • Edited

You actually have a wrong LPS algorithm. Here's the right one:

function calculateLpsTable(subStr) {
    let i = 1;
    let j = 0;
    let lps = new Array(subStr.length).fill(0);

    while(i < subStr.length) {
        if(subStr[i] === subStr[j]) {
            lps[i] = j + 1;
            i += 1;
            j += 1;
        } else {
            if(j !== 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
    }
    return lps;
}

Swastik Yadav • Dec 1 '21

There was a small typo at line 8. Wrote "i" instead of "1".

Thanks for pointing.

Swastik Yadav • Dec 1 '21 • Edited

LPS value is actually correct. It is [0, 0, 0, 1, 2, 0]

I had a small typo in LPS algorithm. I added "i" instead of "1".

Thanks for pointing.

Sanzhar Danybayev • Dec 1 '21

Yeah, that all because of the type. It changed the value and it also causes infinite loop.
Nevertheless that was a pleasure to read your article!

jeevikasirwani • Aug 25 '22

Hey please can you tell me which website did you use to add those code snippets?

Swastik Yadav • Aug 26 '22

Those code snippets are not added via any website. I wrote the article in markdown along with the code, and the snippets' design is native to dev.to platform itself.

Gabriel Genellina • Dec 1 '21

You got the O(n^2) complexity wrong. O(n^2) is quadratic complexity, a special case of polynomial complexity O(n^k).
Exponential complexity is O(2^n) and none of your example algorithms have exponential complexity.

Swastik Yadav • Dec 2 '21

Yes, you are right. Thaks for this. I will fix it soon.

slidenerd • Dec 1 '21

wouldnt life be amazing if everything was O(1)

Lazar Eric • Dec 20 '22 • Edited

Wonderful post, thank you.

Radix sort improvement to handle negative integers, in my own writing:

// Including the sign (+,-) 
function maxDigits(array) {
    return Math.max(...array.map(item => String(item).length));
}

function getDigit(value, i) {
    let response = String(value);

    const index = response.length - 1 - i;

    response = index >= 0 ? response[index] : undefined;

    return ['+', '-'].includes(response) ? -1 : !response ? 0 : +response;
}

function radixSort(value) {
    let array = value;
    const digits = maxDigits(array);

    // Digits 
    for (let i = 0; i < digits; i++) {
        // sign, and 10 number digits 0-9, 11 
        const buckets = Array.from({ length: 11 }, () => []);

        // Array 
        for (let j = 0; j < array.length; j++) {
            // -1 for sign, 0 for 0 or no value, and 0-9 for a value 
            const index = getDigit(array[j], i);

            buckets[index + 1].push(array[j]);
        }

        array = buckets.flatMap(item => item);
    }

    return array;
}

Toni Stojev • Oct 31 '22

In binary search, you have an infinite loop for non-existent member search.
Correct while loop exit term should be:

  while (array[middleIndex] !== element && firstIndex !== middleIndex && middleIndex!==firstIndex)

amirkhansinga • Jan 12 '22 • Edited

Very well explain Appreciated your efforts... Really Nice.

Website

Bruno Panassi • Dec 3 '21

This is gold, thank you for sharing this!

Swastik Yadav • Dec 3 '21

Thank you Bruno. 🙏

I am glad that you found this useful. 😊

Alejandro Alexiades • Dec 1 '21

Very nice article, thanks

Swastik Yadav • Dec 1 '21

Thanks for your kind words Alejandro. It means a lot. 😊

Ben Sembira • Aug 27 '22 • Edited

Isn’t it a bit cheating to say that in the radix sort algorithm k x m = n?

I mean, it is true but if the largest number in the array is at least propotional to the size of the array (which is very likely) then k becomes Ω(log m) (lower bound) and in this case for being more fair with the other algorithms, if we define n to be the length of the array we will get something close to O(n log n).

Just putting it here for those who would confuse and think that radix sort is absolutely better then quick sort or merge sort. It depends on the data and the free space you have.

Quick sort is an in place sorting algorithm while radix uses additional O(m) space.
Sorting one million people by their age (as an int) is a classic radix sort example because of the small range numbers can be in, but sorting one million people by the amount of money they have in their bank account will probably do better with quick sort.