Bubble sort is a simple yet fundamental sorting algorithm that every aspiring programmer should understand. It’s a sorting technique that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In this article, we will explore how to implement bubble sort in Python using nested loops and provide clear examples to help you grasp this algorithm’s concepts.
1. Understanding Bubble Sort.
- Before we dive into the Python implementation, let’s understand the basic steps of the bubble sort algorithm.
- Start from the beginning of the list.
- Compare the first two elements. If the first element is greater than the second, swap them.
- Move one position forward and repeat step 2.
- Continue this process until you reach the end of the list.
- After completing one pass, the largest element will have “bubbled up” to the end of the list.
- Repeat steps 2 – 6 for the remaining unsorted elements until the entire list is sorted.
2. Bubble Sort Python Implementation with Nested Loops.
2.1 Example Source Code.
- Now, let’s implement bubble sort in Python using nested loops:
def bubble_sort(arr): n = len(arr) for i in range(n): # Flag to optimize the algorithm swapped = False # Last i elements are already sorted, so we don't need to check them for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: # Swap the elements if they are in the wrong order arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # If no two elements were swapped in the inner loop, the array is already sorted if not swapped: break # Example usage: my_list = [64, 34, 25, 12, 22, 11, 90] bubble_sort(my_list) print("Sorted array is:", my_list)
- In the code above, we first determine the length of the input array (`arr`).
- We use two nested loops. The outer loop (`for i in range(n)`) runs for `n` passes, where `n` is the number of elements in the list.
- The inner loop (`for j in range(0, n – i – 1)`) performs the pairwise comparisons and swaps.
- We also use a `swapped` flag to optimize the algorithm. If no swaps are made during a pass through the inner loop, the array is already sorted, and we can break out of the outer loop early.
2.2 Example Output.
- Let’s see how the algorithm works with the provided example:
my_list = [64, 34, 25, 12, 22, 11, 90] bubble_sort(my_list) print("Sorted array is:", my_list)
Sorted array is: [11, 12, 22, 25, 34, 64, 90]
- Bubble sort is a straightforward sorting algorithm that can be easily implemented in Python using nested loops.
- While it is not the most efficient sorting algorithm for large lists, understanding bubble sort is essential for grasping sorting algorithms’ concepts and principles.
- By following the step-by-step guide and examples provided in this article, you should have a solid foundation for implementing bubble sort and exploring more advanced sorting algorithms in Python.