Bubble Sort
Tags: dsawithkunal, python, java, algorithms
Published: 2021-09-10 13:52:33

<h1><strong>Introduction</strong></h1>

<p><strong>Bubble sort</strong>&nbsp;is&nbsp;a sorting algorithm&nbsp;that compares two adjacent elements and swaps them until they are not in the intended order. It&nbsp;is the simplest sorting algorithm.<br />
&nbsp;</p>

<h1><strong>How does Bubble Sort work?</strong></h1>

<p>Suppose we have an array [-2, 45, 0, 11,-9] that we are willing to sort in ascending order.</p>

<h4><strong>1. First Iteration or First Pass</strong></h4>

<ol>
	<li>Starting with&nbsp;index zero, compare the first and second elements.</li>
	<li>If the first element is greater than the second element, swap them.</li>
	<li>Compare the second and third elements, and swap them if the second element is greater than the third element.</li>
	<li>Repeat the above process till the last element<br />
	<br />
	<img alt="" src="https://cdn.programiz.com/cdn/farfuture/kn1zM7ZGIj60jcTe3mv8gAtbrvFHqxgqfQ7F9MdjPuA/mtime:1582112622/sites/tutorial2program/files/Bubble-sort-0.png" /></li>
</ol>

<h4><strong>2. Remaining Iteration</strong></h4>

<p>The same process goes on for the remaining iterations. We will notice that <em>after each iteration, the largest element among the unsorted elements is placed at the end.</em></p>

<p><em><img alt="" src="https://cdn.programiz.com/cdn/farfuture/LzbPYkOXS-DjqwLqtIrixMZCD1XLdU-JWWedrL1YIpw/mtime:1582112622/sites/tutorial2program/files/Bubble-sort-1.png" /></em></p>

<p>In each iteration, the comparison takes place up to the last unsorted element.</p>

<p><img alt="" src="https://cdn.programiz.com/cdn/farfuture/-C5A9EpPrCAwR2TFQlZhG0uy5aSKmq-ewMaWyXp8_a8/mtime:1582112622/sites/tutorial2program/files/Bubble-sort-2.png" /></p>

<p>The array is sorted when all the unsorted elements are placed at their correct positions.</p>

<p><img alt="" src="https://cdn.programiz.com/cdn/farfuture/NnXQeMGuMJnIH0qzC1C5n7r4FOynP9vu3cWEdCK5Qjk/mtime:1582112622/sites/tutorial2program/files/Bubble-sort-3.png" /><br />
&nbsp;</p>

<h1><strong>Algorithm</strong></h1>

<pre>
<code>bubbleSort(array)
  for i &lt;- 1 to indexOfLastUnsortedElement-1
    if leftElement &gt; rightElement
      swap leftElement and rightElement
end bubbleSort</code></pre>

<p>&nbsp;</p>

<h1><strong>Code Implementation</strong></h1>

<h4><u><strong>In Java</strong></u></h4>

<pre>
<code>package algorithms.sorting;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {-2, 45, 0, 11,-9};
        BubbleSort bs = new BubbleSort();
        int swaps = bs.sort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(&quot;Total swaps done : &quot; + swaps);
    }

    public int sort(int[] arr) {
        int swaps = 0;

        for (int i = 0; i &lt; arr.length; i++) {
            for (int j = 1; j &lt; arr.length - i; j++) {
                if (arr[j] &lt; arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    swaps++;
                }
            }
        }
        return swaps;
    }
}
</code></pre>

<h4><br />
<u><strong>In Python</strong></u></h4>

<pre>
<code>def bubble_sort(array):
    swaps = 0
    for i in range(len(array)):
        for j in range(1, len(array) - i):
            if array[j] &lt; array[j - 1]:
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
                swaps += 1

    return swaps


if __name__ == &#39;__main__&#39;:
    nums = [-2, 45, 0, 11, -9]
    total_swaps = bubble_sort(nums)
    print(nums)
    print(f&quot;Total swaps done : {total_swaps}&quot;)
</code></pre>

<h4><br />
<u><strong>Output</strong></u></h4>

<pre>
<code>[-9, -2, 0, 11, 45]
Total swaps done : 6</code></pre>

<p>&nbsp;</p>

<h1><strong>Optimized Bubble Sort Algorithm</strong></h1>

<p>One thing, we can notice in the above algorithm is that even if the array is already sorted, the comparisons are still done which is useless.&nbsp;This increases the execution time.</p>

<p>To solve this, we can take an extra boolean variable&nbsp;<code>swapped</code> or <code>isSwapped</code> which is set to <strong>true</strong> if there occurs swapping of elements. Otherwise, it is set&nbsp;<strong>false</strong>.&nbsp;</p>

<p>After an iteration, if there is no swapping, the value of&nbsp;<code>swapped</code> or <code>isSwapped</code>&nbsp;will be&nbsp;<strong>false</strong>. This means elements are already sorted and there is no need to perform further iterations.</p>

<p>This will reduce the execution time and helps to optimize the bubble sort.<br />
&nbsp;</p>

<h1><strong>Algorithm for Optimized Bubble Sort</strong></h1>

<pre>
<code>bubbleSort(array)
  swapped &lt;- false
  for i &lt;- 1 to indexOfLastUnsortedElement-1
    if leftElement &gt; rightElement
      swap leftElement and rightElement
      swapped &lt;- true
end bubbleSort</code></pre>

<p>&nbsp;</p>

<h1><strong>Code Implementation</strong></h1>

<h4><u><strong>In Java</strong></u></h4>

<pre>
<code>package algorithms.sorting;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {-2, 45, 0, 11,-9};
        BubbleSort bs = new BubbleSort();
        int swaps = bs.sort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(&quot;Total swaps done : &quot; + swaps);
    }

    public int sort(int[] arr) {
        boolean isSwapped;
        int swaps = 0;

        for (int i = 0; i &lt; arr.length; i++) {
            isSwapped = false;
            for (int j = 1; j &lt; arr.length - i; j++) {
                if (arr[j] &lt; arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    isSwapped = true;
                    swaps++;
                }
            }
            if (!isSwapped) break;
        }
        return swaps;
    }
}
</code></pre>

<p>&nbsp;</p>

<h4><u><strong>In Python</strong></u></h4>

<pre>
<code>def bubble_sort(array):
    swaps = 0
    for i in range(len(array)):
        is_swapped = False
        for j in range(1, len(array) - i):
            if array[j] &lt; array[j - 1]:
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
                is_swapped = True
                swaps += 1

        if not is_swapped:
            break

    return swaps


if __name__ == &#39;__main__&#39;:
    nums = [-2, 45, 0, 11, -9]
    total_swaps = bubble_sort(nums)
    print(nums)
    print(f&quot;Total swaps done : {total_swaps}&quot;)
</code></pre>

<p>&nbsp;</p>

<h4><u><strong>Output</strong></u></h4>

<pre>
<code>[-9, -2, 0, 11, 45]
Total swaps done : 6</code></pre>

<p>&nbsp;</p>

<h3><strong>Bubble Sort Complexity</strong></h3>

<table border="0">
	<tbody>
		<tr>
			<th><strong>Time Complexity</strong></th>
			<td>&nbsp;</td>
		</tr>
		<tr>
			<td>Best</td>
			<td>O(n)</td>
		</tr>
		<tr>
			<td>Worst</td>
			<td>O(n^2)</td>
		</tr>
		<tr>
			<td>Average</td>
			<td>O(n^2)</td>
		</tr>
		<tr>
			<th><strong>Space Complexity</strong></th>
			<td>O(1)</td>
		</tr>
		<tr>
			<th><strong>Stability</strong></th>
			<td>Yes</td>
		</tr>
	</tbody>
</table>

<p>&nbsp;</p>

<h3><strong>Detailed Complexity</strong>&nbsp;</h3>

<p>Bubble Sort compares the adjacent elements.</p>

<table border="0">
	<tbody>
		<tr>
			<th>Cycle</th>
			<th>Number of Comparisons</th>
		</tr>
		<tr>
			<td>1st</td>
			<td>(n-1)</td>
		</tr>
		<tr>
			<td>2nd</td>
			<td>(n-2)</td>
		</tr>
		<tr>
			<td>3rd</td>
			<td>(n-3)</td>
		</tr>
		<tr>
			<td>.......</td>
			<td>......</td>
		</tr>
		<tr>
			<td>last</td>
			<td>1</td>
		</tr>
	</tbody>
</table>

<p>&nbsp;Hence, the number of comparisons is</p>

<pre>
<code>(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2</code></pre>

<p>which is nearly equal to <strong>n^2</strong></p>

<p>Hence,&nbsp;<strong>Complexity:</strong>&nbsp;<strong><var>O(n^2)</var></strong><br />
&nbsp;</p>

<h1><strong>Time Complexity</strong></h1>

<ul>
	<li><strong>Worst Case Complexity:</strong>&nbsp;<code>O(n^2)</code><br />
	If we want to sort in ascending order and the array is in descending order then&nbsp;the worst case occurs.</li>
	<li><strong>Best Case Complexity:</strong>&nbsp;<code>O(n)</code><br />
	If the array is already sorted, then there is no need for sorting.</li>
	<li><strong>Average Case Complexity:&nbsp;</strong><code>O(n^2)</code><br />
	It occurs when the elements of the array are in jumbled order (neither ascending nor descending).</li>
</ul>

<h1><br />
<strong>Space Complexity</strong></h1>

<ul>
	<li>Space complexity is&nbsp;<code>O(1)</code>&nbsp;because an extra variable is used for swapping.</li>
	<li>In the&nbsp;<strong>optimized bubble sort algorithm</strong>, two extra variables are used. Hence, the space complexity will be&nbsp;<code>O(2)</code>.</li>
</ul>

<p>&nbsp;</p>

<h1><strong>Conclusion</strong></h1>

<p>In this blog, we discussed the first sorting algorithm - Bubble Sort. This blog post cannot end without thanking the person who has motivated a lot of students to learn DSA, that too free of cost -&nbsp;<strong><a href="https://www.linkedin.com/in/kunal-kushwaha/">Kunal Kushwaha</a></strong>&nbsp;and&nbsp;<a href="https://www.linkedin.com/company/commclassroom/"><strong>Community Classroom</strong></a>. You can also access his free DSA playlist&nbsp;<a href="https://www.youtube.com/playlist?list=PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ">here</a>.</p>

<p>Image Courtesy: <a href="https://www.programiz.com/">Programiz</a><br />
Visualize algorithms easily on <a href="http://visualgo.net/">visualgo.net</a>.</p>