Bubble sort

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Sorting algorithms

Deeply studied
Solve how to sort an unsorted collection in ascending/descending order
Can reduce complexity of problems
Some sorting algorithms:
- bubble sort
- selection sort
- insertion sort
- merge sort
- quicksort

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element and another pointer that points to the second element.

First value greater than the second value

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element and another pointer that points to the second element. The first and the second elements have been swapped.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the second element and another pointer that points to the third element.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the third element and another pointer that points to the forth element.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the third element and another pointer that points to the forth element. The third and the forth elements have been swapped.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the forth element and another pointer that points to the fifth element.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the forth element and another pointer that points to the fifth element. The forth and the fifth elements have been swapped.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the forth element and another pointer that points to the fifth element. The fifth element is colored in blue because it is ordered.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element and another pointer that points to the second element. The last element is colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the second element and another pointer that points to the third element. The last element is colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the second element and another pointer that points to the third element. The second and the third elements have been swapped. The last element is colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the third element and another pointer that points to the forth element. The last element is colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the third element and another pointer that points to the forth element. The last two elements are colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element and another pointer that points to the second element. The last two elements are colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the second element and another pointer that points to the third element. The last two elements are colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element and another pointer that points to the second element. The last four elements are colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort

A schematic representation of a list with unordered numbers. There is one pointer that points to the first element and another pointer that points to the second element. All the elements are colored in blue.

First value greater than the second value
- Swap them
Second value greater than the first value
- Nothing

Bubble sort - implementation

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]

Bubble sort - implementation

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list

Bubble sort - complexity

Worst case: $O(n^2)$
Best case - not improved version: $\Omega(n^2)$
Best case - improved version: $\Omega(n)$
Average case: $\Theta(n^2)$
Doesn't perform well with highly unsorted large lists
Performs well:
- large sorted/almost sorted lists
- small lists

Let's practice!

Data Structures and Algorithms in Python