Be the first user to complete this post

  • 1
 Add to List
Beginner

321. Bubble Sort and Optimized Bubble Sort

In this article we will discuss about what is bubble sort, why it is considered as one of the simplest sorting algorithm, what its complexity, how we can improve the bubble sort algorithm.

What is bubble sort??

  • Bubble sort is one of the simplest sorting algorithms.
  • Bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order.
  • The pass through the list is repeated until no swaps are needed, that means array is sorted.
  • As the name indicates, the lighter elements (smaller) ‘bubble up’ to the top.
  • Bubble sort is also known as sinking sort (heavy or bigger elements settles down at the bottom of the list after each iteration).

Time Complexity: O(N2)

Let’s walk through on example:

bubble Sort Logic


Pros and cons of Bubble sort:

  • Pros: Bubble sort algorithm is considered as very simple sorting technique since all you need to do is compare all the adjacent elements and swap them if they are in wrong order.
  • Cons: Main drawback of bubble sort is its time complexity which is O(N2) since all the pairs are compared, even when the original array is sorted.

Output:

Original Array: [5, 1, 9, 3, 2, 10]
Sorted Array: [1, 2, 3, 5, 9, 10]

How we can improve Bubble sort:

  • As see in the program above, bubble sort compares all the pairs in the array, even when original array is sorted or partially sorted. This is where we can do some improvements.
  • During any iteration, if there are no swaps then we can claim that our array is already sorted.

Output:

Original Array: [5, 1, 9, 3, 2, 10]
Sorted Array: [1, 2, 3, 5, 9, 10]
------------------------------
Original Array: [1, 2, 4, 6, 8, 10]
Sorted Array: [1, 2, 4, 6, 8, 10]

Reference: Wiki

Related Problems: