Bubble Sort¶

Bruteforce approach¶

Use the following property:

• In each round, the largest element will bubble up and get arranged into it's desired position.
• For the first loop, we'd need n-1 rounds first of all

• The second loop will be required to do comparison between adjacent element

  • This loop need not run upto the length of the array each time the first loop is run. Why?
  • This is because at each iteration of the parent loop, the largest element will bubble up thus leaving only the remaining array sorted. So we can do range(1, len(arr)-i)

• For each ith round, we move the ith largest element to the right place or to the right of the array

• Time Complexity:

  • Best case: $O(n^{2})$
  • Worst Case: $O(n^{2})$

• Space Complexity: $O(1)$

In [1]:

def bubble(arr):

    for i in range(len(arr)):
        for j in range(1, len(arr) - i):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]

    return arr

def bubble(arr): for i in range(len(arr)): for j in range(1, len(arr) - i): if arr[j - 1] > arr[j]: arr[j - 1], arr[j] = arr[j], arr[j - 1] return arr

In [2]:

arr = [10, 1, 7, 6, 14, 9]
arr = [10, 9, 8, 7, 6, 5]
arr = [1, 2, 3, 4, 5]

arr = [10, 1, 7, 6, 14, 9] arr = [10, 9, 8, 7, 6, 5] arr = [1, 2, 3, 4, 5]

In [3]:

bubble(arr)

bubble(arr)

Out[3]:

[1, 2, 3, 4, 5]

Slight optimization¶

• Time Complexity:

  • Best case: $O(n)$
  • Worst Case: $O(n^{2})$

• Space Complexity: $O(1)$

In [4]:

def bubble_optimized(arr):
    for i in range(len(arr)):
        is_sorted = False
        for j in range(1, len(arr) - i):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
                is_sorted = True

        if not is_sorted:
            break
    return arr

def bubble_optimized(arr): for i in range(len(arr)): is_sorted = False for j in range(1, len(arr) - i): if arr[j - 1] > arr[j]: arr[j - 1], arr[j] = arr[j], arr[j - 1] is_sorted = True if not is_sorted: break return arr

In [5]:

arr = [64, 25, 12, 22, 11]
arr = [10, 9, 8, 7, 6, 5]
arr = [1, 2, 3, 4, 5]

arr = [64, 25, 12, 22, 11] arr = [10, 9, 8, 7, 6, 5] arr = [1, 2, 3, 4, 5]

In [6]:

bubble_optimized(arr)

bubble_optimized(arr)

Out[6]:

[1, 2, 3, 4, 5]

In [ ]: