Bubble Sort
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
Visualization
Details
Analogy
Imagine people lining up for a photo, ordered by height. You compare each pair of adjacent people and swap them if the taller person is on the left. You repeat this pass until no more swaps are needed, and the line is perfectly ordered from shortest to tallest.
Purpose
To sort an array of elements by repeatedly swapping adjacent elements that are out of order. The pass through the list is repeated until the list is sorted.
Use Cases
Primarily used for educational purposes due to its simplicity. It is not suitable for large datasets as its average and worst-case time complexity are quite high.
Algorithm Steps
function bubbleSort(array):
n = length(array)
for i = 0 to n - 1:
swapped = false
for j = 0 to n - i - 2:
if array[j] > array[j + 1]:
swap(array[j], array[j + 1])
swapped = true
if not swapped:
break
return array
Explanation
What's Happening?
Start of Pass 1. Compare the first two elements: 5 and 3.
Code Implementation
def 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
return arr