An Introduction to Bubble Sort

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written blog posts about Binary Search, Linear Search, Interpolation Search, Sorting Algorithms, Selection Sort, Insertion Sort, Merge Sort and Quick Sort.

This blog post I will focus on Bubble Sort. I will explain what Bubble Sort is, how Bubble Sort is associated with Algorithms, try to break down Bubble Sort step by step and provide an example.

What is Bubble Sort and how is it associated with Algorithms?

Bubble Sort is a sorting algorithm, which is commonly used in computer science. Bubble Sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order.

Bubble Sort Algorithm: Steps on how it works:

1. In an unsorted array of 5 elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater).
2. Compare the second and third element to check which one is greater, and sort them in ascending order.
3. Compare the third and fourth element to check which one is greater, and sort them in ascending order.
4. Compare the fourth and fifth element to check which one is greater, and sort them in ascending order.
5. Repeat steps 1–5 until no more swaps are required.

Below is an image of an array, which needs to be sorted. We will use the Bubble Sort Algorithm, to sort this array:

And here is another image:

Bubble Sort: An example

Here is an example of writing the Bubble Sort Algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameter: an array. The function returns the sorted array.

Some Characteristics of Bubble Sort:

• Large values are always sorted first.
• It only takes one iteration to detect that a collection is already sorted.
• The best time complexity for Bubble Sort is O(n). The average and worst time complexity is O(n²).
• The space complexity for Bubble Sort is O(1), because only single additional memory space is required.

Overall Bubble Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over other sorting algorithms.