Bubble sort algorithm in JavaScript

Question

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); 

Answer 1

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.

Answer 2

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)

Answer 3

When dealing with sorting algorithms, it can be useful to add some more detailed logging so that you can see what is going on, or step through the code in a debugger.

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)

Answer 4

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.

Answer 5

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.