Bubble Sort Algorithm

Pic by Mika Baumeister on Unsplash

Today, I’m gonna discuss Bubble Sort Algorithm. Like Insertion Sort Algorithm, bubble sort is another important sorting algorithm in Data Structures that always comes up in interviews and once you understand it fully you can easily implement it in your favourite programming language such as Python, C++ or Java.

Let’s get started.

In the bubble sort algorithm, we scan the array from left to right.

Suppose we have an array of integers. Our task is to sort the given array in increasing order. Those items which are out of order we swap them.

8, 2, 4, 1, 3

Compare the first two integers at index 0 and 1. If the right item is smaller than the left one, we will swap them and the resulting array is:

2, 8, 4, 1, 3

Now, compare the items at index 1 and 2. Again look at the right integer. If it is smaller than the left integer swap them with each other.

The resulting array is:

2, 4, 8, 1, 3

Then do the same procedure again and again unless 8 reaches its final position.

2, 4, 1, 8, 3

Then,

2, 4, 1, 3, 8

So, integer 8 is in its correct position. We don’t need to swap 8 again.

In this way, our first iteration is completed. We need multiple iterations or passes to fully sort this array. After each pass, the next largest item bubbles up and moves to its correct position.

Now start the next iteration. First, you need to compare the first two items which are 2 and 4. In this case, 4 is larger so you do not need to move it. Then compare 4 with 1. As 4 is larger than 1 so swap it with 1 like this.

2, 1, 4, 3, 8

Now, compare 4 with 3 and swap each other.

2, 1, 3, 4, 8

So, we see that 4 is now in its correct location and we don’t need to swap it further.

In the final step, we need to compare the first two integers 2 and 1 and swap them and you see the array is fully sorted.

1, 2, 3, 4, 8

We don’t need to swap 3 as it is already in its correct location. By swapping these numbers we have now our final array.

1, 2, 3, 4, 8

Time Complexity

In the best-case scenario, the array is already sorted.

For the best-case scenario Time Complexity is 0(n), Linear.

In the worst-case scenario, the array is sorted in reverse order.

For the worst-case scenario Time Complexity is 0(n²), Quadratic.

Reference for this article:

https://www.youtube.com/watch?v=uJLwnsLn0_Q

--

--

--

I write about Computer Science, Tech and Literature.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Getting Started with Web Components & Lit | Part 3

From Teaching to Programming: Why I Joined a Coding Bootcamp Hackbright for a Career Change

Introduction to HTML and categorized HTML tags reference

An introduction to Caduceus decentralized edge rendering technology — how does it work and what…

The Top 5 Underrated Linux Networking Tools

Using PyInvoke and Docker to create the ultimate code-base control center

Introduction to StarRocks

Architecture of StarRocks

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Salman Maken

Salman Maken

I write about Computer Science, Tech and Literature.

More from Medium

Arrays, what are they essentially?

Array Data Structures

Find All Numbers Disappeared in an Array (space complexity O(n) and O(1)

Two Sum Using Python