16. Bubble Sort: Concept and Implementation (O(N²))

Bubble Sort is the simplest sorting algorithm, but also one of the least efficient. It is primarily used for educational purposes.

Concept

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest elements 'bubble up' to the end of the list with each pass.

Implementation Steps

1. Start at the beginning of the list.
2. Compare the current element with the next element.
3. If the current element is greater, swap them.
4. Repeat this until the end of the list.
5. Repeat the entire process N-1 times (or until no swaps occur in a pass).

python def bubble_sort(arr): n = len(arr) for i in range(n): # Last i elements are already in place for j in range(0, n - i - 1): # Swap if the element found is greater than the next element if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr