Adrian

Posted on May 17, 2020

What’s your alternative solution? Challenge #45

#challenge #javascript #codenewbie #learntocode

About this series

This is series of daily JavaScript coding challenges... for both beginners and advanced users.

Each day I’m gone present you a very simple coding challenge, together with the solution. The solution is intentionally written in a didactic way using classic JavaScript syntax in order to be accessible to coders of all levels.

Solutions are designed with increase level of complexity.

Today’s coding challenge

Implement the bubble sort algorithm for an array of numbers

(scroll down for solution)

Code newbies

If you are a code newbie, try to work on the solution on your own. After you finish it, or if you need help, please consult the provided solution.

Advanced developers

Please provide alternative solutions in the comments below.

You can solve it using functional concepts or solve it using a different algorithm... or just solve it using the latest ES innovations.

By providing a new solution you can show code newbies different ways to solve the same problem.

Solution

// Solution for challenge40

var ar = [23, 1000, 1, -1, 8, 3];
println(ar);
bubbleSort(ar);
println(ar);

function bubbleSort(ar)
{
    var shouldSort = true;

    while(shouldSort)
    {
        shouldSort = false;

        for(var i = 0; i < ar.length - 1; i++)
        {
            var a = ar[i];
            if ( a > ar[i+1] )
            {
                ar[i] = ar[i+1];
                ar[i+1] = a;
                shouldSort = true;
            }
        }
    }
}

To quickly verify this solution, copy the code above in this coding editor and press "Run".

Note: The solution was originally designed for codeguppy.com environment, and therefore is making use of println. This is the almost equivalent of console.log in other environments. Please feel free to use your preferred coding playground / environment when implementing your solution.

Top comments (5)

Jithin KS • May 17 '20 • Edited

Just wanted to try applying clean coding principles in the bubble sort algorithm...

const arrayToSort = [3,5,6,7,8,9]

const bubbleSort = (arrayToSort) => {
  for(let i=0;i<arrayToSort.length;i++) {
    const indexOfLastElementInThePass = arrayToSort.length-i-1
    goAndRearrangeTill(indexOfLastElementInThePass) 
  }
}

const goAndRearrangeTill = (i) => {
  for(let j=0;j<i;j++) {
    if(arrayToSort[j]>arrayToSort[j+1]) {
      swapInPositions(pos1, pos2)
    }
  }
}

const swapInPositons = (pos1,pos2) => {
  let temp = arrayToSort[pos1]
  arrayToSort[pos1] = arrayToSort[pos2]
  arrayToSort[pos2] = temp
}

bubbleSort(arrayToSort)
console.log(arrayToSort)```

js

Mike Talbot ⭐ • May 18 '20

Damn I hate being a critic and you could surely have a go at a whole bunch of my code with good reason! But I thought I'd write this as a start of a discussion point if you like. While I like the long variable names in parts and the fact that it does bubble -

Declaring functions as const arrows is just ugly and does stuff you don't need, costing performance. I'd also say it makes it much harder to read and also means you have to be careful about the order of things, which proper functions get around. I'd leave fat arrow functions for a place where you need to capture the "this" of the outer function and not in the heart of tight loops (e.g. in a search inner loop).
The (i) variable in goAndRearrangeTill isn't very clear, especially as it's the "maximumIndexToSort" and one of the key principles of the algorithm. An uneducated reader might not work out what was going on there.
While it bubbles, it does not terminate immediately on a collection that is in order before the iterations are complete, making it far less efficient in the case data is in order compared to the original.
There aren't that many places that we need to work about performance and the cost of calling nested functions, but a sort loop is probably one of them. All of those calls to swapInPositions feel a little costly. They also cost 6 lines of code adding to comprehension complexity compared to 1 line to actually do the swap in place using modern JS. [arrayToSort[j], arrayToSort[j+1]] = [arrayToSort[j+1], arrayToSort[j]]

Jithin KS • May 19 '20

Wow, thanks for the response.

I really would like to understand how arrow function costs performance because currently, I don't use the function syntax anywhere. I consider the arrow function as the function in JS. I really need to know if I want to change that habit.
I'm well aware that the algorithm does not have a terminating condition if its already sorted, I just didn't want to make it more complicated.
Yes, I do agree about the swap, what you said is more suitable there.

Mike Talbot ⭐ • May 19 '20

So arrow functions make a class that captures the current "this" and provide it through to the inner function. It's not a massive cost, but it's additional to the cost of calling a function in both memory and instructions. It makes total sense if you need the "this" and indeed all functions declared in the body of another create a class to carry around the bound closure variables - but there is no such cost for a globally defined function.

Declaring any const requires that the code is executed before using the variable.

This works:


     doSomething() 

     function doSomething() { console.log('ok'); }

This does not:


     doSomething();
     const doSomething = ()=>console.log("Nope!");

Mike Talbot ⭐ • May 18 '20

Just to point out, your algorithm presented doesn't actually bubble making it much slower. In a bubble sort we guarantee that one element bubbles to the end of the list. We never need to consider it again. So while that bubbling will happen to the array elements in your code, we never get the benefit of it.


var ar = [23, 1000, 1, -1, 8, 3];
println(ar);
bubbleSort(ar);
println(ar);

function bubbleSort(ar)
{
    var shouldSort = true;
    var length = ar.length;

    while(shouldSort)
    {
        shouldSort = false;
        length--;
        for(var i = 0; i < length; i++)
        {
            var a = ar[i];
            if ( a > ar[i+1] )
            {
                ar[i] = ar[i+1];
                ar[i+1] = a;
                shouldSort = true;
            }
        }
    }
}

DEV Community

What’s your alternative solution? Challenge #45

About this series

Today’s coding challenge

Code newbies

Advanced developers

Solution

Top comments (5)

Read next

react-native duplicate class problem

The mysterious supply chain concern of string-width-cjs npm package

Image with text overlay using HTML and CSS

10 Best Live Streaming SDKs in 2024