bubbelsort

Bubbelsort, commonly known in English as bubble sort, is a simple comparison-based sorting algorithm. The idea is to repeatedly pass through a list, compare adjacent values, and swap them if they are out of order. After each pass, the largest unsorted element moves to its final position, much like bubbles rising to the surface, hence the name.

The typical implementation uses two nested loops: the outer loop tracks the number of passes, and the inner loop compares adjacent elements and performs swaps when needed. The process continues until a complete pass occurs with no swaps, indicating the list is sorted. Because each swap moves an element at most one position per pass, bubbelsort is stable: equal elements retain their relative order.

Time and space complexity: In the worst and average case, bubbelsort transverses the list in O(n^2) time. If an optimized version is used that stops when no swaps occur, its best case is O(n) for an already sorted or nearly sorted list. The algorithm sorts in place and uses only a small, constant amount of extra space, making it memory-efficient but not scalable for large datasets.

Variants and practical notes: An optimized version reduces unnecessary comparisons on sorted lists. A bidirectional variant, sometimes called cocktail shaker sort, traverses the list in both directions each pass. In practice, bubbelsort is largely superseded by more efficient algorithms for large datasets, but it is commonly taught for its simplicity and its role in illustrating sorting concepts.