DEV Community

Yigal Ziskand
Yigal Ziskand

Posted on • Edited on

Bubble Sort (3 min recap)

Motivation

It's shiny benefit is it's implementation simplicity, but be aware (it comes with a heavy price) it should not be applied on large datasets since its performance is O(n)^2 which is quite... terrible...

Basic Idea

The basic idea is very simple - we should go over each item in our collection by comparing the current item with its right closes neighbor.
In case we find that the left item is bigger then right one [left > right] - we simply switch their places and continue to the next neighbors.

This way we make sure that the biggest number is always BUBBLED UP to the most right place.
If we continue this procedure for each item in the collection then we can claim that we have incrementally sorted collection of items

Pseudo Code

done = false
while !done
    done = true
    for i = 0 .. items.length
        if items[i] > items[i + 1]
            swap(a[i], a[i + 1])
            done = false
Enter fullscreen mode Exit fullscreen mode

Code Snippet

  let dataSet = [1, 6, 2, 3, 4, 5, 7];

  const bubbleSort = () => {
    let done = false;
    while (!done) {
      done = true;

      for (let i = 0; i < dataSet.length; i++) {
        if (dataSet[i] && dataSet[i + 1] && dataSet[i] > dataSet[i + 1]) {
          [dataSet[i], dataSet[i + 1]] = [dataSet[i + 1], dataSet[i]];

          done = false;
        }
      }
    }
  };
Enter fullscreen mode Exit fullscreen mode

Example

Since Svelte compiler allows us to write almost identical to standard JS - i have sketched a simple example of the algorithm triggered by a button click.
BubbleSort (Svelte REPL)

Top comments (2)

Collapse
 
ashiquedesai profile image
Ashique

This is a nice little example of bubble sort for beginners.

Collapse
 
ziskand profile image
Yigal Ziskand • Edited

yep, its just a short recap of the algorithm (3 min target)