Bubble sort

D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
So ware 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

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort

First value greater than the second value

Swap them

Second value greater than the rst value

Nothing

DATA STRUCTURES AND ALGORITHMS IN PYTHON

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]

DATA STRUCTURES AND ALGORITHMS IN PYTHON

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

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Bubble sort - complexity
Worst case: O(n2 )
Best case - not improved version: Ω(n2 )
Best case - improved version: Ω(n)
Average case: Θ(n2 )
Doesn't perform well with highly unsorted large lists

Performs well:
large sorted/almost sorted lists

small lists

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N
 Selection Sort and
Insertion Sort
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
So ware engineer
Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort

Determine the lowest value

Swap the lowest value with the rst unordered element

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort - implementation
def selection_sort(my_list):
list_length = len(my_list)
for i in range(list_length - 1):
lowest = my_list[i]
index = i
for j in range(i + 1, list_length):
if my_list[j] < lowest:
index = j
lowest = my_list[j]
my_list[i] , my_list[index] = my_list[index] , my_list[i]
return my_list

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Selection sort - complexity
Worst case: O(n2 )
Average case: Θ(n2 )
Best case: Ω(n2 )

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort - implementation
def insertion_sort(my_list):
for i in range(1, len(my_list)):
number_to_order = my_list[i]
j = i - 1
while j >= 0 and number_to_order < my_list[j]:
my_list[j + 1] = my_list[j]
j -= 1
my_list[j + 1] = number_to_order
return my_list

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Insertion sort - complexity
Worst case: O(n2 )
Average case: Θ(n2 )
Best case: Ω(n)

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N
 Merge sort
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
So ware engineer
Merge sort
Follows divide and conquer
Divide
divides the problem into smaller sub-problems

Conquer
sub-problems are solved recursively

Combine
solutions of sub-problems are combined to achieve the nal solution

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - implementation
def merge_sort(my_list): while i < len(left_half):
if len(my_list) > 1: my_list[k] = left_half[i]
mid = len(my_list)//2 i += 1
left_half = my_list[:mid] k += 1
right_half = my_list[mid:]
merge_sort(left_half) while j < len(right_half):
merge_sort(right_half) my_list[k] = right_half[j]
j += 1
i = j = k = 0 k += 1
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
my_list = [35,22,90,4,50,20,30,40,1]
my_list[k] = left_half[i] merge_sort(my_list)
i += 1 print(my_list)
else:
my_list[k] = right_half[j]
[1, 4, 20, 22, 30, 35, 40, 50, 90]
j += 1
k += 1

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Merge sort - complexity
Worst case: O(n log n)
signi cant improvement over bubble sort, selection sort, and insertion sort

suitable for sorting large lists

Average case: Θ(n log n)

Best case: Ω(n log n)
other algorithms (e.g. bubble sort, insertion sort) have be er best case complexity

Space complexity: O(n)

worst space complexity than other algorithms with O(1)
Other variants reduce this space complexity

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N
 Quicksort
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
So ware engineer
Quicksort
Follows divide and conquer principle

Implemented by many programming languages

Partition technique
Pivot

items smaller than the pivot -> le

items greater than the pivot -> right

Elements to the le will be sorted recursively

Elements to the right will be sorted recursively

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - in action

Hoare's partition
Move le pointer until a value greater than pivot is found

Move right pointer until a value lower than pivot is found

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - implementation
def quicksort(my_list, first_index, last_index):
if first_index < last_index:
partition_index = partition(my_list, first_index, last_index)
quicksort(my_list, first_index, partition_index)
quicksort(my_list, partition_index + 1, last_index)

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - implementation
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
while my_list[left_pointer] < pivot and left_pointer < last_index:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - implementation
my_list = [6, 2, 9, 7, 4, 8]
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Quicksort - complexity
Worst case: O(n2 )
Very e cient!
Average case: Θ(n log n)
Best case: Ω(n log n)
Space complexity: O(n log n)

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Let's practice!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N
 Congratulations!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N

Miriam Antona
So ware engineer
Chapter 1
What algorithms and data structures are Calculate time complexity using Big O
Notation
Linked lists

Stacks

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Chapter 2
Queues Trees

Hash tables
Graphs
my_menu = {
'lasagna': 14.75,
'moussaka': 21.15,
'sushi': 16.05
}

Recursion

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Chapter 3
Searching algorithms: Binary search trees
Linear search

Binary search

Depth rst search

Breadth rst search

DATA STRUCTURES AND ALGORITHMS IN PYTHON

Chapter 4
Sorting algorithms
Bubble sort

Selection sort

Insertion sort

Merge sort

Quicksort

DATA STRUCTURES AND ALGORITHMS IN PYTHON

 Thank you!
D ATA S T R U C T U R E S A N D A L G O R I T H M S I N P Y T H O N