BubbleSort

Bubble sort is a simple, comparison-based sorting algorithm. It operates by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are out of order. With each pass, the largest remaining unsorted element moves to its final position at the end of the list, so the suffix grows sorted.

Algorithm:

- for i from 0 to n-2

- swapped = false

- for j from 0 to n-i-2

- if a[j] > a[j+1]

- swap a[j] and a[j+1]

- swapped = true

- if not swapped then break

Complexity and properties:

Bubble sort’s worst-case and average time complexity are O(n^2); the best case is O(n) when the array is already sorted and an early-exit flag is used. The algorithm uses O(1) additional space and is in place. It is a stable sort, meaning equal elements retain their relative order.

Variations and performance:

Optimizations include reducing the inner loop bound as the end of the array becomes sorted, and using an early-exit flag to stop when no swaps occur in a pass. A bidirectional variant called cocktail shaker sort traverses the list in both directions. While simple and easy to implement, bubble sort is impractical for large datasets compared with faster algorithms such as quicksort, mergesort, or heapsort.

Use cases:

Bubble sort is primarily of educational value and is suitable for very small datasets or situations where code clarity matters more than performance. It is often used to illustrate sorting concepts before introducing more advanced algorithms.

---