9
\$\begingroup\$

I'm new to JavaScript (and programming) and taking a course. I was tasked with creating a bubble sort on any array using JavaScript. Of course, since this is an algorithm challenge, no sort method allowed. After I wrote this, I looked around at other implementations of bubble sort. I only found one that used a similar algorithm. Most set a variable to true or false to exit the loop.

I'm curious if the way I've written this is valid, efficient, and even a bubble sort at all -- since I don't loop through the entire array at any point (unless edge case is the array is already sorted). I know there are tons of bubble sort questions out there, but I couldn't find one exactly like this.

//Bubble Sort algorithm practice for JavaScript class

arrayX = [1,9,-1,5,10,23,-2,7,4,5,1];

for (i = 0; i <= arrayX.length-1; i++)
  {
    if (arrayX[i] > arrayX[i+1])
      {
        temp = arrayX[i+1];
        arrayX[i+1] = arrayX[i];
        arrayX[i] = temp;
        i = i-2;
      }
  }
console.log(arrayX);
\$\endgroup\$
  • 1
    \$\begingroup\$ I was almost VTC'ing your question because it really didn't look like a correct sorting implementation to me. Upon testing it quickly, I discovered that it is indeed sorting correctly. Sneaky way of fooling me like that. \$\endgroup\$ – Simon Forsberg Apr 24 '15 at 17:16
  • 1
    \$\begingroup\$ Had literally same reaction as @SimonAndréForsberg. I don't mean to discourage experimentation, it is indeed a clever trick, but I would advise against "false advertising". If we were on the same team and for whatever reason we needed bubble sort, then I'd either expect to see either a classical implementation or a comment remark on what's different (and why). \$\endgroup\$ – Inoryy Apr 25 '15 at 6:04
8
\$\begingroup\$

Let me start with the interesting question:

Is it even a bubble sort?

This sort is a bit like bubble sort and a bit like insertion sort. You have re-invented gnome sort, so congratulations, that's a nice coup for a beginner.

The other answers -- which state that you should not access arrays out-of-bounds, and should use var to declare local variables rather than relying on automatic declaration to save you, are correct. To that basic advice I would add the following:

  • Make a sorting function that takes an array as its argument
  • Now that you have such a function, write test cases. Don't forget to test already-sorted arrays, empty arrays, arrays with one, two, or three elements, arrays sorted into reverse order, and so on.

That's the basic stuff. A more advanced technique that you should start using now is

  • clearly state your loop invariants in comments or, better, assertions

A loop invariant is something that you believe to be true no matter what at various points in the loop. For example, a loop invariant that you have violated is "the index is always in bounds".

By clearly stating your invariants you can then analyze the code to see if it correctly maintains the invariants. If it does, then you have more confidence that the code is correct.

The loop invariant of bubble sort is "after n iterations, the last n elements are in their proper place".

The loop invariant of gnome sort is "everything to the left of i is sorted".

I'm curious if the way I've written this is valid, efficient, and even a bubble sort at all

Though the code uses poor practices that have already been discussed, it appears to be a valid sort.

It is not, as sorts go, efficient. Asking whether a bubble sort (or bubble sort variation) written in JavaScript is efficient is a bit like asking which of two pet turtles is the faster; if you care about speed then you've chosen the wrong pet.

\$\endgroup\$
6
\$\begingroup\$

It is good practice to create variables with the var keyword.

So instead of this:

arrayX = [1,9,-1,5,10,23,-2,7,4,5,1];

You would add the var keyword and get this:

var arrayX = [1,9,-1,5,10,23,-2,7,4,5,1];

By not having the var keyword, you are creating a global variable, which means that other variables will not be able to share the same name as that variable without affecting the original variable (which can prove troublesome with iteration variables like i)

\$\endgroup\$
5
\$\begingroup\$

When dealing with sorting algorithms, it can be useful to add some more detailed logging so that you can see what is going on.

I created a JSFiddle where I added some logging so that we can see what exactly is going on.

The results of these loggings indicates a problem with your code: You are accessing index -1 and index arrayX.length at times, which only contains undefined data.

Your for-loop loops over one element too many, it should be

for (i = 0; i < arrayX.length-1; i++)

(Note that I changed <= to <)

Additionally, after i = i-2; (which could be i -= 2; btw), it can have a negative number. Make sure that i never goes below 0 here. (or technically -1, as it is increased by one directly after)

\$\endgroup\$
  • \$\begingroup\$ JavaScript does seem to be forgiving with accessing indexes out of the array. \$\endgroup\$ – Launa Apr 24 '15 at 17:36
  • \$\begingroup\$ @Launa Yes, it is, but that being said, it is still good to avoid accessing undefined indexes. \$\endgroup\$ – Simon Forsberg Apr 24 '15 at 17:51
  • \$\begingroup\$ Would it be acceptable to set i = -1 rather than i = i-2? It works and doesn't ever access a negative index. How would I go about testing its efficiency against the traditional bubble sort algorithm? \$\endgroup\$ – Launa Apr 24 '15 at 18:21
  • \$\begingroup\$ @Launa setting it directly to i = -1 would make your algorithm slower. You can use a tool such as jsperf.com to test your codes performance. Implement your own version, and also add a 'real' version and see their differences. (Remove all unnecessary console.log calls and similar before you run the tests) \$\endgroup\$ – Simon Forsberg Apr 24 '15 at 18:35
  • \$\begingroup\$ Using JSPerf (thanks for that btw) I ran a 'traditional' bubble sort vs. my variation (i = -1). The traditional is considerably faster. Interestingly, the i = i-2 variation is slower than i = -1. I imagine this depends on how the numbers are ordered in the array to some degree. You can see the tests here if you're interested. Test Results \$\endgroup\$ – Launa Apr 24 '15 at 19:14
1
\$\begingroup\$

Here's my solution to the bubble sort, it's quite long, but pretty easy to read without much help from sort methods provided by javascript:

/* Bubble Sort */

var x = [6,5,3,1,8,7,2,4];

function bubbleSort(a) {

// Variables for BubbleSort
  var empty = [];
  var counter = a.length;
  var last = 0;
  var secondCounter = 0;

// Variables for reversing

  var reverseCount = 0;
  var secondReverseCount = a.length - 1;

// Bubble Sort

    while (secondCounter < a.length){
      for (var i = 1; i < a.length; i++) {

        if (a[i -1] > a[i]) {
          var temp = a[i-1];
          a[i-1] = a[i];
          a[i] = temp;

        }
      }
      last = a[counter - 1];
      empty[secondCounter++] = last;
      counter--;
    }

// We have to reverse it now

  while (reverseCount < secondReverseCount) {

    var temp2 = empty[reverseCount];
    empty[reverseCount] = empty[secondReverseCount];
    empty[secondReverseCount] = temp2;

    reverseCount++;
    secondReverseCount--;
  }

  return empty;
}




console.log(bubbleSort(x));

Here's the link to a gif that shows how the bubble sort works:

http://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif

My logic for this is to loop through each number of the given array, then swap the 1st and 2nd, the 2nd to 3rd, and so forth. If the number is higher then the number to the right then it will swap, but if not, it will not swap.

I then save the last number from the swap transition and store it in my empty array. Then I cut off the array by one number at the end and loop through it again and do the same thing.

The numbers now stored in the empty array are in the wrong order so I had to do a while loop to reverse the values stored in my Empty Array.

From there I return that value stored in my empty array.

\$\endgroup\$
  • \$\begingroup\$ Hi! Welcome to Code Review. Please add more context to your answer, such as explain why your code is better. At Code Review, we do not like code dumps. \$\endgroup\$ – TheCoffeeCup May 18 '15 at 16:58
1
\$\begingroup\$

It is usually not good practice to get into the habit of putting curly brackets on separate lines as JavaScript has automatic semicolon insertion.

More info here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.