DEV Community

Cover image for Bubble Sort In JavaScript

Bubble Sort In JavaScript

Emma Bostian ✨ on May 10, 2019

Bubble Sort is one of the most widely discussed algorithms, simply because of its lack of efficiency for sorting arrays. If an array is already sor...
Collapse
 
karataev profile image
Eugene Karataev

Two years ago on interview I was asked to write bubble sort on a paper. I guess it's the only sorting algorithm I can write without google help 😀

I'm a visual learner, so it's useful for me to visualize an algorihtm process. I created the bubble sort visualization to better grasp the concept.

bubble sort

You can fork and play with it here.

Collapse
 
hamzaerbay profile image
Hamza ERBAY

Thanks, Emma for the explanation.
Eugene, I m another visual learner too :) I want to put visualgo.net here. That's super helpful for understanding algorithms.

Collapse
 
karataev profile image
Eugene Karataev

Yeah, visualgo is a great resource to grasp algorithms by visualizing them step by step.

Collapse
 
emmabostian profile image
Emma Bostian ✨

Horrible interview!

Collapse
 
jcklpe profile image
Aslan French

I'm a designer who is learning to code and I found this a little confusing.

I don'tunderstand why you're nesting stuff the way you are in code. How can there be two ways of writing the code if the essential logical idea of the sort is the same?

Why do you callthem pointers? I thought pointers were a thing in c++ for telling a program where stuff was stored in memory?

Also I didn't understand what o(n^2) meant. I'm guessing that as the array length grows, the number of operations required grows exponentially? But why?

Collapse
 
victorcorcos profile image
Victor Cordeiro Costa • Edited

Hello! You are confused because you never studied Algorithm Analysis or Complexity Analysis. It is basically the study of algorithm performance... this course is the core of a Computer Scientist degree, for example!

1) How can there be two ways of writing the code if the essential logical idea of the sort is the same? => When analysing algorithms, you will discover it is common to do the same thing in a lot of different manners. The main idea can be the same, but the way it is executed is different. Both of the versions of this Bubble Sort are looping through the array items a lot of times (more than N times, where N is the number of items in the array). Both of the versions also have the same idea of bubble sort, which is: Comparing pair of elements and swap them in a way that on the end of each loop, the highest element will be in the end of the array. You can discover that by running the bubbleSortConcept2 on your browser, by running this: bubbleSortConcept2([5, 4, 3, 2, 1]). It will show you the resulting array after each loop, which is: An array that have the highest element on the end of it. This is the main idea of bubble sort and both algorithms are doing that!

2) Why do you callthem pointers? => Pointers doesn't exist only in C++ or C level. In fact, most part of the languages (or all of them) use pointers inside. Some very high-level languages (Java, Ruby, Python, R, ...) just hide that information to you, but it is using the pointers in the depths, since these high-level languages convert the code to a low-level language and they need to deal with pointers! C/C++ are considered high-level languages, but in a lower dimension than the ones I just mentioned, since C/C++ needs to make you deal pointers. I will try to be very succinct: Pointers are just variables that points to another variables. That's it. (In deep therms, it points to a memory address of another variable, but you can study more of that if you want). Now, let's go to the first sorting example... The i and the j variables are pointers, because they points to the position (index) of an element in the array. :) On the second sorting example, the index is the pointer, for the same reason.

3) Also I didn't understand what o(n2) meant => Yeah, that is a bit complex to explain to you, as it envolves the core of Algorithm Analysis, haha, but I will try. The N is the array length, as you noticed. The algorithm loop through the array length more than N times, the question is: Can you figure out how many comparisons (if's) this algorithm will have on the total? This will show the nature of the bubble sort. You can check the quantity of comparisons by adding this comparisonCount here...

function bubbleSortConcept1(arr) {
  var comparisonCount = 0

  for (let j = arr.length - 1; j > 0; j--) {
    for (let i = 0; i < j; i++) {
      comparisonCount++
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }

  console.log('N (length): ', arr.length)
  console.log('Comparisons: ', comparisonCount)
}
Enter fullscreen mode Exit fullscreen mode

Here are some results:

bubbleSortConcept1([2, 1])
N (length): 2
Comparisons: 1

bubbleSortConcept1([3, 2, 1])
N (length): 3
Comparisons: 3

bubbleSortConcept1([4, 3, 2, 1])
N (length): 4
Comparisons: 6

bubbleSortConcept1([5, 4, 3, 2, 1])
N (length): 5
Comparisons: 10

bubbleSortConcept1([6, 5, 4, 3, 2, 1])
N (length): 6
Comparisons: 15

bubbleSortConcept1([7, 6, 5, 4, 3, 2, 1])
N (length): 7
Comparisons: 21

bubbleSortConcept1([20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
N (length):  20
Comparisons:  190
Enter fullscreen mode Exit fullscreen mode

As you can see, the quantity of Comparisons is growing much more faster than the N (length), this indicates that the order of magnitude of this algorithm is greater than N, now you need to find the order of magnitude in which the Comparisons is greater than the N (length).
You need to find the equation that gives you the quantity of Comparisons based on the N (length). On the bubble sort, this equation is:

c = n(n - 1)/2
Enter fullscreen mode Exit fullscreen mode

You can verify it applying to different examples, let's take the last one...

bubbleSortConcept1([20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
N (length):  20
Comparisons:  190

// Replacing it on the equation you found...
c = 20(20 - 1)/2
c = 20(19)/2
c = 380/2
c = 190
// 190 comparisons
Enter fullscreen mode Exit fullscreen mode

Now, why it is O(n^2) after all of this explanation?
n(n - 1)/2 is the same as: (n^2 - n)/2.
You need to study what is the O notation / Big O notation to enter on the details, but, in summary, you need to extract the function that grows faster on this equation: (n^2 - n)/2.

n^2 grows faster than n ? Yes! So it is O(n^2)

Collapse
 
jcklpe profile image
Aslan French

Thank you, this was super helpful! Your explanation of how n2 works was in particular useful.

Collapse
 
emmabostian profile image
Emma Bostian ✨

This goes back to the principles of computer science, so you might want to read up on those principles if you're confused.

There are many different ways to write code, there's never just one answer.

Pointers are just that; pointers to a spot in an array. They keep track of the index we're at. I could have called them anything as they're just variables.

O(N2) refers to the run time. Because we're comparing every element with every other element, and Big-O refers to the worst-case scenario or upper-bound, the most comparison's you'll have to do is N * N.

Collapse
 
jcklpe profile image
Aslan French

Thanks. Reading up on those basics is a big part of what I've been trying to do lately, one reason why I found your article. Thanks!

Collapse
 
moremooredesign profile image
Jeremy Moore

I was curious as to what sorting algorithm JavaScript uses, and apparently there's no universal specification. Different browsers seem to use different algorithms.

bugzilla.mozilla.org/show_bug.cgi?...

Collapse
 
codeguppy profile image
Adrian

Super cool Emma!
I want also to point to a bubble sort visualizer built in JavaScript.

codeguppy.com/code.html?visual_sort

Collapse
 
yeeiodev profile image
Pablo Yev

Did you create this content?? It was very clear and right now I am looking for references just like this. Thanks!

Collapse
 
emmabostian profile image
Emma Bostian ✨

Haha yes I created it. Why would I post it if I hadn't? :P

Collapse
 
yeeiodev profile image
Pablo Yev

You are right!! What I meant was if all the material was made by you or you got it from a book or something. I'm a visual learner and the way you presented the info was very clear for me.

Thread Thread
 
emmabostian profile image
Emma Bostian ✨

Ahh yeah haha I see. No I create them all myself using Sketch :)

Collapse
 
the24thds profile image
David Sima

I'm sure that this is very good content for the beginners! Good job with this one :) Waiting for the next one.

Collapse
 
shoyeb_memon profile image
memon shoyeb

Loved this ! great explanation emma !!

Collapse
 
johnylab profile image
João Ferreira • Edited

Thank you but... aaammm... what else. I'm curious if there are some green solutions.

Collapse
 
joshhadik profile image
Josh Hadik

Unfortunately there aren’t any green solutions for sorting an array.

This seems kind of inefficient at first but if you think about it it kind of makes sense. Best case scenario an array is already sorted, which logically still takes N steps since you have to walk through each element of the array to know it’s sorted.

But usually the array won’t be sorted, which means you still have to take N steps, plus even more steps to actually do the work of sorting the array, which is where we get second N in O(N2).

You can do better than N2 by using certain algorithms like merge sort, but even then you’re still limited by the fact that you have to touch every element at least once, plus you have to take extra steps to reorganize the content of the array, and it turns out the most efficient way you can do this is in O(N log N) time.

Collapse
 
micrajesh profile image
Mic • Edited

Didn't run/test yet but has the doubt in Concept 2 Code: what about arr[index + 1] when at the last item is coming in the iteration.. will it be array index out bounds ?