Python Bubble Sort

Bubble Sort Example Python: Step-by-Step Walkthrough

To get a better understanding of the Python bubble sort algorithm, let us discuss a step-by-step example in detail, taking an unsorted list as our input.

Consider the following list as our input:

• 5
• 1
• 4
• 2
• 8

We will now walk through the steps taken by the bubble sort algorithm to sort this list in ascending order:

1. Compare the first two elements (5 and 1). Since 5 > 1, swap them:
       1, 5, 4, 2, 8
2. Move to the next pair (5 and 4). Swap them as 5 > 4:
       1, 4, 5, 2, 8
3. Continue the process with the next pair (5 and 2) and swap them:
       1, 4, 2, 5, 8
4. Proceed to the next pair (5 and 8). As 5 < 8, no swap is needed.

Since an entire pass took place without any swaps needed, the list is considered sorted and the algorithm terminates.

Here is a Python code implementation of the bubble sort algorithm:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

arr = [5, 1, 4, 2, 8]
bubble_sort(arr)
print("Sorted array is:", arr)

Implementing Bubble Sort in Python

The basic implementation of the Python bubble sort algorithm can be achieved using a function, such as 'bubble_sort', that takes a list as its argument and performs the sorting process through nested loops. The outer loop iterates through all the elements of the list, whilst the inner loop compares adjacent elements and swaps them if they are out of order. The inner loop's range decreases during each iteration to prevent comparing sorted elements.

Here's a sample Python code demonstrating the basic implementation of bubble sort:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

• Define a function named 'bubble_sort' that takes a list 'arr' as input.
• Calculate the length of the list (n) using the 'len' function.
• Use a 'for' loop to iterate through all elements in the list (outer loop).
• Using a nested 'for' loop (inner loop), iterate through the remaining unsorted elements and compare adjacent pairs.
• If the current element (arr[j]) is greater than the element to its right (arr[j+1]), swap them using the 'swap' operation.
• After the loops finish executing, the sorted list 'arr' is printed.

Bubble Sort Algorithm Python: Optimised Version

An optimised version of the bubble sort algorithm improves its performance, especially for partially sorted or nearly sorted lists. This optimisation can be achieved by adding a variable that tracks whether any swaps occurred during an iteration. If no swaps occur, the algorithm terminates, as the list is already sorted. This early termination can save a significant amount of time in certain cases.

Below is the Python code for the optimised version of bubble sort:

def optimised_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

arr = [64, 34, 25, 12, 22, 11, 90]
optimised_bubble_sort(arr)
print("Sorted array is:", arr)

• Introduce a 'swapped' variable before the inner loop to track any swaps made during each iteration of the outer loop.
• Set 'swapped' to 'True' inside the inner loop whenever a swap is performed.
• After each iteration of the inner loop, check the value of 'swapped'. If it remains 'False', it signifies that no swaps were made, indicating that the list is already sorted and the algorithm can terminate early.

Both basic and optimised implementations provide an understanding of the bubble sort algorithm in Python. By using them efficiently in various scenarios, you can optimise your code and achieve better performance while sorting elements in your lists or arrays.

Applications of Python Bubble Sort

Python Bubble Sort algorithm is commonly implemented in various programming and real-life scenarios for its simplicity, ease of implementation, and understanding. In this section, we discuss some use cases where bubble sort can be effectively used to sort different types of data such as strings and practical applications in computer science.

Bubble Sort Alphabetical Order Python: Sorting Strings

Bubble sort is not limited to sorting numeric values, it can also be employed to sort strings in alphabetical order. This requires the comparison of two string elements to determine the correct sequence. By comparing the Unicode values of characters in each string, bubble sort can arrange strings in alphabetical order.

Here is a detailed walkthrough of the process:

1. Convert each string element to a reference character, often the first character of the string.
2. Compare the Unicode value of these reference characters to decide the order of the two strings.
3. Swap the strings if they are found in the incorrect order based on their reference characters.
4. Iterate through the list of strings, repeatedly sorting and swapping until the entire list is arranged in alphabetical order.

An example Python code implementation for sorting a list of strings would look like this:

def bubble_sort_strings(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

string_list = ["banana", "apple", "orange", "grape", "cherry"]
bubble_sort_strings(string_list)
print("Alphabetically sorted list:", string_list)

With the above implementation, the input list of strings is sorted in alphabetical order based on their reference character comparison, which in this case is their first character.

Practical Use Cases of Python Bubble Sort in Computer Science

While Python Bubble Sort has its limitations in terms of complexity and efficiency, it remains a popular sorting technique in various practical applications where simplicity and ease of implementation are more important, especially in the following cases:

1. Educational Purposes: Bubble Sort serves as an introductory technique for teaching sorting algorithms to beginners as it is easy to comprehend and implement compared to more complex algorithms such as Merge Sort and Quick Sort.

2. Small Datasets: With small datasets, bubble sort's simplicity and in-place sorting capabilities can outweigh its performance drawbacks, making it a suitable option for sorting relatively small amounts of data.

3. Nearly Sorted Datasets: When applied to a list that is already partially sorted, the optimised version of the bubble sort algorithm can terminate early, making it efficient for certain scenarios where the data is already in an almost sorted state.

4. Restricted Environment Applications: In some cases, computational resources and memory might be limited, and using more complex algorithms might not be feasible. In such constrained environments, bubble sort can be a valuable alternative.

In summary, Python Bubble Sort is useful for specific applications where simplicity, ease of implementation, and educational potential are prioritised over time complexity. Although other sorting algorithms are more efficient for large datasets or complex data structures, bubble sort continues to serve as a practical solution in some cases, especially for new learners in computer science and in constrained computing environments.