Bubble Sort


By Riolku
Written 26 days ago

Bubble sort is a very simple sorting algorithm, although it is still rather inefficient.

The idea is to pass through the array, considering each pair of elements. If they are out of order, they are swapped. This is continued until the array is sorted.

In the worst case, the minimum element is last in the array, and it will take \( N - 1 \) passes to get it to the start. Therefore, the time complexity is \( \mathcal O(N^2) \).

Here is a very basic bubble sort implementation in python.

def bubble_sort(arr):
  for i in range(len(arr) - 1):
    for j in range(len(arr) - 1):
      if arr[j] > arr[j + 1]:
        # swap the elements, since they are out of order
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
  
  return arr