Python Coding Test Course, Bubble Sort Program 1

This lecture explains the process of solving basic algorithm problems using Python.
In this session, we will take a closer look at one of the most fundamental sorting algorithms, Bubble Sort.
Bubble Sort is a simple yet easy-to-understand sorting algorithm that helps in understanding the basics of algorithms.

1. What is Bubble Sort?

Bubble Sort is an algorithm that sorts by comparing two adjacent elements.
It goes through each element of the list sequentially, swapping them when two adjacent elements are in the wrong order.
This process is repeated, which is why it is named Bubble Sort, as the largest element “bubbles” up to the end of the list.

1.1. The working process of Bubble Sort

The basic working process of Bubble Sort is as follows:

  1. Start from the first element of the list and compare two adjacent elements.
  2. If the first element is greater than the second element, swap their positions.
  3. Repeat until the end of the list to send the largest element to the very end.
  4. Excluding the last element of the list, go back to step 1 and repeat for the remaining part.
  5. Continue this process until all elements in the list are sorted.

2. Implementing the Bubble Sort Algorithm

Now, let’s implement Bubble Sort in Python code. Here is the basic code for the Bubble Sort algorithm. 

def bubble_sort(arr):
    n = len(arr)
    # Repeat for the length of the list
    for i in range(n):
        # In each pass, the last i elements are already sorted, so repeat until n-i-1
        for j in range(0, n-i-1):
            # Compare and swap adjacent elements
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

2.1. Code Explanation

The above code defines a function called bubble_sort, which takes a list to be sorted as an argument.

  • n = len(arr): Stores the length of the given list.
  • The outer for loop repeats for all elements of the list.
  • The inner for loop compares adjacent elements in the currently unsorted part and swaps them if necessary.
  • Returns the sorted list after all passes are completed.

3. Bubble Sort with an Example

Let’s actually use Bubble Sort to see it in action with an example.

3.1. Example List

Let’s sort the following list: [64, 34, 25, 12, 22, 11, 90]

3.2. Step-by-Step Explanation of the Sorting Process

1. First Pass:

  • Compare 64 and 34 → Swap → [34, 64, 25, 12, 22, 11, 90]
  • Compare 64 and 25 → Swap → [34, 25, 64, 12, 22, 11, 90]
  • Compare 64 and 12 → Swap → [34, 25, 12, 64, 22, 11, 90]
  • Compare 64 and 22 → Swap → [34, 25, 12, 22, 64, 11, 90]
  • Compare 64 and 11 → Swap → [34, 25, 12, 22, 11, 64, 90]
  • Compare 64 and 90 → No Swap → [34, 25, 12, 22, 11, 64, 90]

The largest number, 90, has bubbled up to the end.

2. Second Pass:

  • Compare 34 and 25 → Swap → [25, 34, 12, 22, 11, 64, 90]
  • Compare 34 and 12 → Swap → [25, 12, 34, 22, 11, 64, 90]
  • Compare 34 and 22 → Swap → [25, 12, 22, 34, 11, 64, 90]
  • Compare 34 and 11 → Swap → [25, 12, 22, 11, 34, 64, 90]
  • Compare 34 and 64 → No Swap → [25, 12, 22, 11, 34, 64, 90]

The second largest number, 64, has moved to the second last position.

By repeating this process, we eventually obtain the sorted list [11, 12, 22, 25, 34, 64, 90].

4. Time Complexity

The time complexity of Bubble Sort is O(n²) in the worst case. This means that the time taken grows proportionally to the square of the length \( n \) of the list.
However, in the best case scenario of dealing with an already sorted list, it can be reduced to O(n).
This occurs because no swaps happen during the first pass.

5. Improvements on Bubble Sort

While Bubble Sort has the advantage of being simple to implement, it has the drawback of being inefficient.
In practical use, the following improvements can be applied:

  • You can terminate the sort immediately if no swaps occur, reducing unnecessary iterations.
  • During the maximum pass, you can avoid comparing the already sorted part and reduce the range of comparisons.

6. Conclusion

In this session, we learned the basic concept of Bubble Sort and how to implement it in Python.
Bubble Sort may be a simple algorithm, but it is very useful for understanding sorting concepts.
If you want to build a foundation in algorithms, start by understanding Bubble Sort!