Bubble Sort

Introduction

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Why Bubble Sort- When to Use

Bubble sort is a simple sorting algorithm used to rearrange a set of elements in ascending or descending order. It can prove to be useful when the number of elements are less.

When to Not Use

This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

Bubble Sort is useful for smaller sets of elements but is inefficient for larger sets.

Other Names of Bubble Sort

Bubble sort algorithm is also known as Sinking Sort, or Exchange Sort.

How does Bubble Sort Work- The Algorithm

After each pass in a bubble sort, the largest element (in the unsorted array), will come at its correct position.
Therefore, with the first pass through the array, the largest element is positioned at the end. With the second pass, the second largest, and so on.

Complexity-Analysis

Space-Complexity= O(1)

No extra-space is required, since we are not creating any new array neither copying an existing array.
These types of algorithms are also, known as in-space sorting algorithms.
Therefore, Bubble Sort is an In-Space Sorting Algorithm.

Time-Complexity:

• Best-Case= O(N); when the array is already sorted.
• Worst-Case= O(N^2); when the array is sorted in opposite direction.

note:- N: No. of comparisons needed.

Stable or Unstable Sorting Algorithm

Bubble Sort is a Stable Sorting Algorithm
A stable sorting algorithms is one which maintain the relative order of records with equal values.

Code

You can have a look at the implementations of Bubble Sort here.

Code-Analysis

Now this is an extra part that I would like to add in this post. If you were looking for a basic understanding of bubble sort, and the most-efficient program for it, we are basically done in the above parts, and you can totally skip this last part.

But if you would like to analyze the program for bubble sort even more, you are welcome to the paragraphs below.

So, we already saw the most-efficient code for bubble sort above. But is that the only code that can be written? I mean, the basic rule of bubble sort algorithm is that check for two adjacent elements, and swap them if they are at their wrong positions.

The basic code for bubble sort can be written as follows-

def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):
            if arr[j]>arr[j+1]:
                # swap
                # so that the largest number is sent to the end of the array
                arr[j],arr[j+1]=arr[j+1],arr[j]
    return arr

It is after running the above code that we begin to notice things.
We can observe that for every pass, we do not need to check for the entire array, since after each pass, the last element comes at its correct position.
Hence, instead of running the nested loop for the entire length of the array, we run it only till the (length- no. of current pass)
That is, for an array of length n, we need to run the nested loop only till n- no. of current pass- 1 (n-i-1).

Also, if you notice, for a particular value of i, if there is no swap happening, that means that the array has already been sorted and we do not need to compare any more.
Hence, we can break the loop if there is no swap, and return the array.

Addition of these small points in our basic code leads us to the most-efficient code for the bubble-sort algorithm, which has been provided in the post above.

So that was all about bubble sort.
Thanks for reading.
Feel free to share your views. 😄.
Also, do not forget to like if found useful! 👍