Bubble Sort

Data Structures and Algorithms are fundamental concepts in programming and software engineering. Bubble Sort is one of the most popular sorting algorithms due to its simplicity and ease of implementation. It is an in-place comparison-based sorting algorithm that can be used to sort a collection of elements, such as an array or a list. In this article, we will discuss how Bubble Sort works in detail, its time complexity (best, average, and worst cases), and its space complexity (worst). We will also look at some examples of Bubble Sort written in Python.

What is Bubble Sort?

Bubble Sort is an algorithm that works by going through an array of elements and swapping adjacent elements if they are out of order. This process is repeated until the array is sorted. It is a simple sorting algorithm that is often used to introduce the concept of sorting algorithms to beginners.

How Does Bubble Sort Work?

As mentioned before, Bubble Sort works by going through an array of elements, comparing adjacent elements and swapping them if they are out of order. This process is repeated until the array is sorted.

Let’s look at an example. We have an array of numbers: [3, 5, 2, 7, 1]. We will use Bubble Sort to sort this array in ascending order.

First, we compare the first two elements, 3 and 5. Since 3 is less than 5, we do not need to swap them.

Next, we compare the second and third elements, 5 and 2. Since 5 is greater than 2, we need to swap them. Our array now looks like this: [3, 2, 5, 7, 1].

Next, we compare the third and fourth elements, 5 and 7. Since 5 is less than 7, we do not need to swap them.

Finally, we compare the fourth and fifth elements, 7 and 1. Since 7 is greater than 1, we need to swap them. Our array now looks like this: [3, 2, 5, 1, 7].

This is one iteration of the algorithm. We need to repeat this process until the array is sorted. We repeat the process until our array looks like this: [1, 2, 3, 5, 7].

The Bubble Sort algorithm can be broken down into two main steps:

• Compare adjacent elements and swap them if they are out of order.
• Repeat this process until the array is sorted.

Time Complexity

The time complexity of Bubble Sort is determined by the number of iterations or passes that are needed to sort the array. In the best case, the array is sorted in one pass, so the time complexity is O(n). In the average case, the array is sorted in n/2 passes, so the time complexity is O(n2). In the worst case, the array is sorted in n passes, so the time complexity is O(n2).

Space Complexity

The space complexity of Bubble Sort is O(1). This is because the algorithm works in-place, meaning that it does not require any additional storage space.

Examples

Now that we have discussed how Bubble Sort works and its time and space complexities, let’s look at some examples of Bubble Sort written in Python.

First, we will look at a simple example of Bubble Sort.

def bubble_sort(arr):
  # Iterate over the array 
  for i in range(len(arr)-1):
    # Iterate over the unsorted part of the array 
    for j in range(len(arr)-i-1):
      # If an element is out of order, swap it 
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [3, 5, 2, 7, 1]
bubble_sort(arr)
print(arr) # [1, 2, 3, 5, 7]

In the above example, we define a function, bubble_sort(), that takes an array as an argument. Then, we iterate over the array, comparing adjacent elements and swapping them if they are out of order. Finally, we print the sorted array.

Now, let’s look at an example of Bubble Sort using Python’s built-in sorting function.

arr = [3, 5, 2, 7, 1]
arr.sort()
print(arr) # [1, 2, 3, 5, 7]

In the above example, we create an array and then use Python’s built-in sort() function to sort the array. This is a much simpler way to sort an array in Python.

Conclusion

In this article, we discussed Bubble Sort, an in-place comparison-based sorting algorithm. We looked at how the algorithm works in detail, its time complexity (best, average, and worst), and its space complexity (worst). We also looked at some examples of Bubble Sort written in Python.

Exercises

def bubble_sort(arr):
  # Iterate over the array 
  for i in range(len(arr)-1):
    # Iterate over the unsorted part of the array 
    for j in range(len(arr)-i-1):
      # If an element is out of order, swap it 
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

def bubble_sort_iterations(arr):
  count = 0
  # Iterate over the array 
  for i in range(len(arr)-1):
    # Iterate over the unsorted part of the array 
    for j in range(len(arr)-i-1):
      # If an element is out of order, swap it 
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
      count += 1
  return count

def bubble_sort_swaps(arr):
  count = 0
  # Iterate over the array 
  for i in range(len(arr)-1):
    # Iterate over the unsorted part of the array 
    for j in range(len(arr)-i-1):
      # If an element is out of order, swap it 
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
        count += 1
  return count

def bubble_sort_reverse(arr):
  # Iterate over the array 
  for i in range(len(arr)-1):
    # Iterate over the unsorted part of the array 
    for j in range(len(arr)-i-1):
      # If an element is out of order, swap it 
      if arr[j] < arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

def bubble_sort_with_number(arr, num):
  # Iterate over the array 
  for i in range(len(arr)-1):
    # Iterate over the unsorted part of the array 
    for j in range(len(arr)-i-1):
      # If an element is out of order, swap it 
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  # Insert the number into the correct position 
  arr.append(num)
  for i in range(len(arr)-1):
    if arr[i] > num:
      arr[i], arr[-1] = arr[-1], arr[i]
  return arr