[Algorithms] Bubble-Sort

• Bubble sort is an algorithm to sort a list through repeated swaps of adjacent elements.
  • It has a quadratic runtime of O(n^2) since we are running (n-1) swaps n times.

nums = [5, 2, 9, 1, 5, 6]

def swap(arr, index_1, index_2):
temp = arr[index_1]
arr[index_1] = arr[index_2]
arr[index_2] = temp

def bubble_sort(arr):
  for el in arr:
    for i in range(len(arr)-1):
      if arr[i] > arr[i+1]:
        swap(arr, i, i+1)

print("Post-Sort: {0}".format(nums))

# Post-Sort: [1, 2, 5, 5, 6, 9]

• notice that after each iteration, the max value of an array gets placed at the final index.
• we can therefore come up with a more optimzed solution that will reduce the inner loop in relation to the number of iterations in the outer loop to avoid iterating over elements which are correctly placed.

def bubble_sort(arr):
  for i in range(len(arr)):
    # iterate through unplaced elements
    for idx in range(len(arr) - i - 1):
      if arr[idx] > arr[idx + 1]:
        # replacement for swap function
        arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]

---