Bubble sort in Python
Published: 2024-04-14 17:52:34

<div class="autorun example">
<pre>
<code class="language-python">#Optimized bubble sort
def bubble_sort(lst):

  swapped = True
  c = 0
  while swapped == True:
    swapped = False
    for j in range(len(lst)-1):  
      
      if(lst[j]&gt;lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j] #swap the elements
        swapped = True
      c +=1
  return c

#sort a list
L = [9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

bubble_sort(L)  
print("The sorted list is: ", L)</code></pre>
</div>

<p>Bubble sort is the most basic sorting algorithm. Its simplicity makes it suitable for introducing computer science students to sorting algorithms. However, it has an average and worst case running time of <code>O(n<sup>2</sup>)</code>, making it highly inefficient for sorting medium to large dataset.</p>

<p>Bubble sort is highly limited compared to other sorting algorithms and, therefore,&nbsp; not suitable for practical environments beyond educational ones.&nbsp;</p>

<p>Despite its limitations, understanding the operation of bubble sort is essential for you to understand how more advanced sorting algorithms works.</p>

<p>In the following parts we will understand how the bubble sort algorithm operates and how to implement it in Python.</p>

<h2>Bubble sort Algorithm description</h2>

<p>In bubble sort algorithm, each pair of adjacent elements are compared and only swapped if they are not in order. That is , if the first element in the pair is larger than the other element, the elements are swapped.</p>

<p>The swapping of elements happens<strong> in-place</strong> meaning that the original list gets modified.</p>

<p>If we have a <strong>list </strong>of <strong>n </strong>elements, the bubble sort algorithm can be performed through the steps shown below:</p>

<div class="tip">
<ol>
	<li>Compare&nbsp;the first&nbsp;element&nbsp;with the next&nbsp;element after it.</li>
	<li>If the first element is greater:
	<ul>
		<li>Swap the two&nbsp;elements.</li>
	</ul>
	</li>
	<li>Move to the next pair of elements&nbsp;in the list.</li>
	<li>Repeat step1 -3&nbsp;until&nbsp;the end of the list is reached.</li>
	<li>Once no more swaps are needed, the list is sorted.</li>
</ol>
</div>

<p>With the above steps,&nbsp; the largest elements gradually moves<strong>&nbsp;</strong>to the end of the list until the list is sorted.</p>

<h2>Direct Implementation</h2>

<p>To implement bubble sort, you can use nested loops, the following example shows how we can achieve this with <a href="https://www.pynerds.com/python-for-loops/">for </a>loops:</p>

<div class="autorun example">
<p>with nested for loops&nbsp;</p>

<pre>
<code class="language-python">def bubble_sort(lst):

  for i in range(len(lst)-1):
    for j in range(len(lst)-1):  

      if(lst[j]&gt;lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j] #swap the elements

#sort a list
L = [9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

bubble_sort(L)  
print("The sorted list is: ", L)</code></pre>
</div>

<p>The<code> bubble_sort() </code>function does not return any value because the sorting happens to the original list.</p>

<p>As show in the above example, nested for loops provides a much direct way of implementing the bubble sort algorithm, but we can also use nested <a href="https://www.pynerds.com/python-while-loop/">while</a> loops to achieve the same, as shown below.</p>

<div class="autorun example">
<p>with while loops&nbsp;</p>

<pre>
<code class="language-python">def bubble_sort(lst):

  i = 0
  while i &lt;  len(lst):
    j = 0
    while j &lt; len(lst)-1:
      if(lst[j]&gt;lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j]
      j += 1
    i += 1

L = [9, 7, 1, 2, 4, 1, 3, 0, 6, 5, 8]
bubble_sort(L)  
print("The sorted list is: ", L)</code></pre>
</div>

<h2>Optimized Implementation</h2>

<p>The previous implementation of bubble sort has one avoidable performance inefficiency. This is because whether the list is already sorted, not sorted or reverse sorted, the algorithm still finishes with the worst-case running time of <code>O(n<sup>2</sup>)</code>.</p>

<p>Note that if the algorithm moves through the entire list without performing the&nbsp; swap operation on any pair of elements, it means that the list is already sorted.&nbsp;We can, therefore, optimize bubble sort to avoid performing unnecessary comparisons by defining an intermediate variable to check whether a swap operation has taken place or not.</p>

<div class="autorun example">
<p>optimized bubble sort</p>

<pre>
<code class="language-python">def bubble_sort(lst):

  swapped = True
  c = 0
  while swapped == True:
    swapped = False
    for j in range(len(lst)-1):  
      
      if(lst[j]&gt;lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j] #swap the elements
        swapped = True
      c +=1
  return c

#sort a list
L = [9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

bubble_sort(L)  
print("The sorted list is: ", L)</code></pre>
</div>

<p>Optimized bubble sort has a best case running time of <code>O(n)</code>, this is is when the list is already in a sorted state. It still has an average and worst case running time of <code>O(n<sup>2</sup>)</code>.</p>

<h3>Bubble sort&#39;s space and time complexity</h3>

<h4>space complexity</h4>

<p>Bubble sort has a space complexity of O(1) this is because no extra lists are used in its internal logic. The sorting happens directly on the input list without the use of intermediate lists.</p>

<h4>Time complexity</h4>

<p>The <strong>unoptimized</strong> version of bubble sort has a time complexity of O(n<sup>2</sup>) regardless of whether the input list is <strong>already sorted</strong>, <strong>not sorted </strong>or <strong>reverse sorted</strong>.&nbsp;</p>

<p>On the other hand, the time complexity cases of the <strong>optimized </strong>version are as highlighted below:</p>

<ul>
	<li><strong>Best-O(n) </strong>- This happens when the input list is already sorted as we simply traverse through the list once.</li>
	<li><strong>Average-O(n<sup>2</sup>) </strong>- When the input&nbsp;list is not sorted and the elements are in arbitrary order.</li>
	<li><strong>Worst</strong>-<strong>O(n<sup>2</sup>)&nbsp;</strong>- When the input list is reverse sorted and,&nbsp;therefore, the swap operation happens with every comparison.</li>
</ul>

<div class="related"><h3>Related articles</h3><hr><ul><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/introduction-to-data-structures-algorithms/">Introduction to Data Structures & Algorithms</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-stack-data-structure-in-python/">Implement Stack data structure in Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-queue-data-structure-in-python/">Implement Queue data structure in Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-fixed-length-stack-in-python/">Implement Fixed-length stack in Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-inorder-tree-traversal-python/">Implement Inorder Tree Traversal - Python</a></ul></div>