DEV Community

Cover image for Bubble-sort
vazsonyidl
vazsonyidl

Posted on โ€ข Edited on

2 1

Bubble-sort

Cover image from: Unsplash - Kai Dahms

Intro

This is going to be a series about different sorting algorithms, some explanation and a quick demo with solution in JavaScript.

Bubble sort

First of all, let start with the most basic one - bubble sort.
The logic behind bubble sort is the following:

  • starting from the beginning, compare two adjacent elements
  • if the previous one is bigger than the following one, swap those two
  • repeat until there is no element left in the array

This is just one iteration, which guarantees that the biggest element is at the end of the array.

  • repeat this process for every element in the array

Complexity

As you may see, there are several different outcomes, and based on the number of the elements to compare, things quickly can get out of control.

Best case scenario: The elements are ordered > we will do O(n) comparisons.

Worst case scenario: The elements are reverse ordered > we will do O(n2) comparison. It does not look like a problem for 10 elements, but for 1000, there will be a lot of zero after that first leading one. :)

Average scenario: Sadly, the average scenario has the same time complexity as the worst one, which still will be O(n2).

Usage

I think bubble sort is not so problematic, because of its ease to understand. Use it wisely, and use it for small amount of elements. There is nothing wrong with it - up to a minimal amount of elements.

Implementation

Of course, there are a lot of way to implement this, but I will leave mine here for anyone who is interested in. I will link the GitHub repo for this as well.

function bubbleSort(_array) {
  const array = _array;
  for (let i = 0; i < array.length - 1; i++)
    for (let j = 0; j < array.length - i; j++)
      if (array[j] > array[j + 1]) [array[j], array[j + 1]] = [array[j + 1], array[j]];

  return array;
}
Enter fullscreen mode Exit fullscreen mode

Some sneak peak:

  • the easiest way to swap two variables is [a, b] = [b, a] > you do not need a tmp one then
  • you do not have to loop the array until the end every iteration > if the greatest is already at the end (and the nth greatest .. so on) leave that alone

Reference

Repo

Sentry workshop image

Flaky tests got you down?

Learn how to merge your code without having to hit โ€œrerunโ€ every 5 minutes ๐Ÿ˜ฎโ€๐Ÿ’จ

Save your spot now.

Top comments (0)

๐Ÿ‘‹ Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay