Bubble Sort in Python

In Python, the Bubble sort algorithm sorts a collection of elements through iterative comparisons of adjacent items, swapping them when they are out of order. Nevertheless, this method is not effective for handling large datasets. In this article, we will explore Bubble sort and examine its implementation in Python.

How Bubble Sort Works?

Bubble sort initiates by examining an element against its neighboring elements continuously and exchanging it with the adjacent element if it is out of order. Initially, the first two elements are assessed and swapped if necessary. Subsequently, the algorithm moves to the next pair of elements and continues this procedure until it reaches the conclusion of the array. This constitutes a single pass. The procedure is reiterated for multiple passes until the entire array is sorted.

Here is the working of the bubble sort algorithm:

Consider the input array [5, 3, 2, 4]

Step 1: Finding the first largest element

Step 2: Finding the second-largest element

Step 3: Identifying the third largest element, ensuring it is in its proper position.

In this pass, the unsorted array is: [2, 3, 4, 5]

i = 0: [2, 3, 4, 5], assess 2 and 3; since 2 is less than 3, no exchange is necessary, indicating that the array is already in order.

Pseudocode for Bubble Sort

The bubble sort pseudocode examines neighboring elements and exchanges them if they are out of order. This procedure continues until the entire list is sorted.

Procedure BubbleSort(array)

n ← length(array)

for i ← 0 to n - 1 do

for j ← 0 to n - i - 2 do

if array[j] > array[j + 1] then

// Swap array[j] and array[j + 1]

temp ← array[j]

array[j] ← array[j + 1]

array[j + 1] ← temp

end if

end for

end for

End Procedure

Bubble Sort Implementation in Python

Here is a Python code demonstration for executing the bubble sort algorithm on a specified array.

Example

def sort_numbers(data):

size = len(data)

for i in range(size):

for j in range(0, size - i - 1):

if data[j] > data[j + 1]:

data[j], data[j + 1] = data[j + 1], data[j]

return data

# Example usage

numbers = [45, 12, 78, 3, 56, 21, 9]

sorted_numbers = sort_numbers(numbers)

print(sorted_numbers)

Output:

[3, 9, 12, 21, 45, 56, 78]

Explanation:

In the code provided, the function sort_number takes a list called data as its argument and sorts the elements of this list in place. A nested loop within the function is employed to compare neighboring elements, executing a swap when they are found to be out of order. The outer loop ensures that the sorting process continues until all elements of the data are arranged correctly.

Time Complexity of Bubble Sort

It is important to know about time complexity for any algorithm as it shows the efficiency of the algorithm, especially for large data. The time complexity of bubble sort is in each cases, where n shows the length of the list.

• ✅ In the bubble sort algorithm, the outer loop executes "n" times, where n represents the number of items in the list.
• ✅ The inner for loop also iterates n times in the worst scenario. However, as the algorithm progresses, the number of iterations in the list reduces because the largest element is placed in its correct position.
• ✅ In the worst scenario, the comparisons count and swaps are proportional to the square of the number of items present in the list.

Optimizing Bubble Sort in Python

Since bubble sort is not the most efficient method for handling large datasets when compared to other sorting algorithms, various techniques exist to enhance its performance. The bubble sort algorithm can be refined through approaches such as flagged bubble sort, recursion, and cocktail shaker sort. Below is a comprehensive discussion on these methods:

Flagged Bubble Sort

In this optimization technique, a flag variable is utilized to monitor swaps during each pass. If no swaps occur, it indicates that the list is sorted, allowing the algorithm to terminate. Below is the code illustrating the flagged bubble sort:

Example

def flagged_bubble_sort(arr):

n = len(arr)

for i in range(n):

swapped = False

for j in range(0, n - 1 - i):

if arr[j] > arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

swapped = True

if not swapped:

break

return arr

arr = [5, 1, 4, 2, 8]

sorted_arr = flagged_bubble_sort(arr)

print(sorted_arr)

Output:

[1, 2, 4, 5, 8]

Explanation:

In the code provided, the flaggedbubblesort function employs a swapped flag to terminate the loop when the array is sorted. It repeatedly compares and swaps elements that are not in the correct order. With each iteration, the largest element among the unsorted portion is positioned correctly. The loop terminates if no swaps occur during a particular pass.

Recursive Bubble Sort

This version of the bubble sort algorithm utilizes recursion, splitting the list into two segments: the initial element and the rest of the unsorted elements. The algorithm recursively sorts the remaining elements until the entire array is in order. Below is the Python code that illustrates a recursive implementation of bubble sort.

Example

def recursive_bubble_sort(arr, n=None):

if n is None:

n = len(arr)

if n == 1:

return

for i in range(n - 1):

if arr[i] > arr[i + 1]:

arr[i], arr[i + 1] = arr[i + 1], arr[i]

recursive_bubble_sort(arr, n - 1)

arr = [5, 1, 4, 2, 8]

recursive_bubble_sort(arr)

print(arr)

Output:

[1, 2, 4, 5, 8]

Explanation:

The recursive bubble sort algorithm takes an array as its input and has 'n' defaulting to None. When n is None, we initially determine its value, which represents the length of the array. The base case occurs when n equals 1, indicating that the array's length is 1, which is inherently sorted and thus returned. We execute the swapping or sorting operation for the initial pass, followed by a recursive call for the subsequent passes.

The time complexity for this algorithm's optimization technique is O(n) in the best-case scenario. However, in both the average and worst cases, the time complexity is O(n^2). This is because each iteration requires O(n) time to compare adjacent elements and swap them, leading to n recursive calls that each perform O(n) comparisons, resulting in an overall time complexity of O(n^2).

Cocktail Shaker Sort

This algorithm is a modification of bubble sort, known as Bidirectional Bubble Sort, which enhances the traditional bubble sort by organizing the elements of the list in both directions. This approach decreases the number of passes required and enhances the algorithm's efficiency. Refer to the example below for Cocktail Shaker sort.

Example

def cocktail_shaker_sort(arr):

n = len(arr)

swapped = True

start = 0

end = n - 1

while swapped:

swapped = False

for i in range(start, end):

if arr[i] > arr[i + 1]:

arr[i], arr[i + 1] = arr[i + 1], arr[i]

swapped = True

if not swapped:

break

end -= 1

swapped = False

for i in range(end - 1, start - 1, -1):

if arr[i] > arr[i + 1]:

arr[i], arr[i + 1] = arr[i + 1], arr[i]

swapped = True

start += 1

return arr

arr = [5, 1, 4, 2, 8]

sorted_arr = cocktail_shaker_sort(arr)

print(sorted_arr)

Output:

[1, 2, 4, 5, 8]

Explanation:

The code presented defines a function cocktailshakersort that sorts the array in both ascending and descending order during each iteration. This function organizes the array by shifting larger values towards the end and smaller values towards the start. The process persists until no further swaps are required, signaling that the array is fully sorted.

Comparison of Bubble Sort with Other Sorting Algorithms

Sorting algorithms are important, and various optimized algorithms have been introduced to structure the data efficiently. To understand their difference and performance, let's see the comparison of bubble sort with other algorithms.