1. Introduction
The Bubble Sort algorithm is one of the simplest sorting algorithms. It works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm continues this process until no more swaps are needed, which indicates that the list is sorted.
2. Implementation Steps
1. Start iterating from the beginning of the list.
2. Compare each pair of adjacent items.
3. If a pair is in the wrong order, swap them.
4. Continue doing this for each pair of adjacent items until the end of the list is reached.
5. Repeat the above steps for every element in the list.
6. When no more swaps are needed, the list is sorted.
3. Implementation in Python
def bubble_sort(arr):
n = len(arr)
# Traverse through all elements in the list
for i in range(n):
# Set a flag to check if any swaps occurred in this pass
swapped = False
# Last i elements are already in place, so we don't need to check them
for j in range(0, n-i-1):
# Traverse the list from 0 to n-i-1
# Swap if the current element is greater than the next element
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
# If no two elements were swapped in the inner loop, the list is already sorted
if not swapped:
break
return arr
# Test the bubble_sort function
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array:", sorted_arr)
Output:
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Explanation:
1. We define the bubble_sort function that takes a list arr as its argument.
2. Inside the function, we get the length of the list n.
3. We then iterate over the list n times.
4. For each iteration, we set a swapped flag to False. This will help us identify if any swaps occurred in this pass.
5. We then iterate over the list again, this time from the start-up to n-i-1. This is because the last i elements are already in their correct position.
6. Inside the inner loop, if the current element arr[j] is greater than the next element arr[j+1], we swap them.
7. If at the end of an outer loop iteration, no swaps were made, we break out of the loop early. This is an optimization to make the algorithm run faster for nearly sorted lists.
8. Finally, we return the sorted list.
Note: Bubble Sort is not the most efficient sorting algorithm for larger lists, but it serves as a great introduction to the world of sorting algorithms.
Related Algorithms in Python
- Write a Python program for Linear Search and Binary Search
- Selection Sort Algorithm in Python
- Bubble Sort Algorithm in Python
- Bogo Sort Algorithm in Python
- Bucket Sort Algorithm in Python
- Comb Sort Algorithm in Python
- Counting Sort Algorithm in Python
- Heap Sort Algorithm in Python
- Insertion Sort Algorithm in Python
- Merge Sort Algorithm in Python
- Quick Sort Algorithm in Python
- Shell Sort Algorithm in Python
- Interpolation Search Algorithm in Python