Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly compares neighbouring items in a list. If two items are in the wrong order, they are swapped. This process continues until the list is fully sorted.
It is called “bubble sort” because the largest values gradually move, or “bubble”, to the end of the list after each pass.
def bubble_sort(array):
n = len(array)
swapped = True
while swapped and n >= 0:
swapped = False
for i in range(0, n-1):
if array[i] > array[i+1]:
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
swapped = True
n = n - 1
return array
def bubble_sort(array): # Function to sort an array using bubble sort
n = len(array) - 1 # Store the last index of the array
swapped = True # Boolean used to control the loop
while swapped and n >= 0: # Repeat while swaps are happening
swapped = False # Assume no swaps will happen this pass
for i in range(0, n - 1): # Loop through the unsorted part of the array
if array[i] > array[i+1]: # Check if two values are in the wrong order
temp = array[i] # Store first value temporarily
array[i] = array[i+1] # Move second value into first position
array[i+1] = temp # Put stored value into second position
swapped = True # A swap happened
n = n - 1 # Reduce range as largest value is now sorted
return array
- Compare the first two items
- Swap them if needed
- Move to the next pair
- Repeat until the end of the list
- Start again until no swaps are needed
[5, 3, 8, 1] Compare 5 and 3 → swap [3, 5, 8, 1] Compare 5 and 8 → no swap [3, 5, 8, 1] ...
PROCEDURE bubble_sort(list)
DECLARE n INITIALLY length(list)
DECLARE swapped INITIALLY TRUE
WHILE swapped
SET swapped TO False
FOR i = 0 to n-2 DO
IF list[i] > list[i+1] THEN
SET temp TO list[i]
SET list[i] TO list[i+1]
SET list[i+1] TO temp
SET swapped TO TRUE
END IF
END FOR
SET n TO n - 1
END WHILE
END PROCEDURE
Task 1 - Array Ascending
Create a program that sorts the following array into ascending order using bubble sort.
numbers = [7, 3, 9, 1, 5]
Before sort - [7, 3, 9, 1, 5] After sort - [1, 3, 5, 7, 9]
# Main
numbers = [8, 4, 2, 9, 1]
sorted_numbers = bubble_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
def bubble_sort(array):
n = len(array)
swapped = True
while swapped and n >= 0:
swapped = False
for i in range(0, n-1):
if array[i] > array[i+1]:
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
swapped = True
n = n - 1
return array
# Main
numbers = [8, 4, 2, 9, 1]
sorted_numbers = bubble_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
def bubble_sort(array): # Function to sort an array using bubble sort
n = len(array) # Store the length of the array
swapped = True # Boolean to control the loop
while swapped and n >= 0: # Repeat while swaps are happening
swapped = False # Assume no swaps this pass
for i in range(0, n-1): # Loop through the unsorted part of the array
if array[i] > array[i+1]: # Check if values are in the wrong order
temp = array[i] # Store first value temporarily
array[i] = array[i+1] # Move second value into first position
array[i+1] = temp # Put stored value into second position
swapped = True # A swap happened
n = n - 1 # Reduce range as largest value is sorted
return array # Return sorted array
# Main
numbers = [8, 4, 2, 9, 1] # Create array of numbers
sorted_numbers = bubble_sort(numbers) # Call function and store sorted array
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
Task 2 - Array Descending
Create a program that sorts the following array into descending order using bubble sort.
numbers = [7, 3, 9, 1, 5]
Before sort - [7, 3, 9, 1, 5] After sort - [9, 7, 5, 3, 1]
# Main
numbers = [8, 4, 2, 9, 1]
sorted_numbers = bubble_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
def bubble_sort(array):
n = len(array)
swapped = True
while swapped and n >= 0:
swapped = False
for i in range(0, n-1):
if array[i] < array[i+1]:
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
swapped = True
n = n - 1
return array
# Main
numbers = [8, 4, 2, 9, 1]
sorted_numbers = bubble_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
def bubble_sort(array): # Function to sort an array using bubble sort
n = len(array) # Store the length of the array
swapped = True # Boolean to control the loop
while swapped and n >= 0: # Repeat while swaps are happening
swapped = False # Assume no swaps this pass
for i in range(0, n-1): # Loop through the unsorted part of the array
if array[i] < array[i+1]: # Check if values are in the wrong order
temp = array[i] # Store first value temporarily
array[i] = array[i+1] # Move second value into first position
array[i+1] = temp # Put stored value into second position
swapped = True # A swap happened
n = n - 1 # Reduce range as largest value is sorted
return array # Return sorted array
# Main
numbers = [8, 4, 2, 9, 1] # Create array of numbers
sorted_numbers = bubble_sort(numbers) # Call function and store sorted array
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
Task 3 - Shortest to Longest
Create a program that sorts an array of words from the shortest word to the longest word.
words = ["elephant", "cat", "giraffe", "dog"]
Before sort - ["elephant", "cat", "giraffe", "dog"] After sort - ["cat", "dog", "giraffe", "elephant"]
# Main
words = ["elephant", "cat", "giraffe", "dog"]
sorted_words = bubble_sort_length(words)
print("Before sort -", words)
print("After sort -",sorted_words)
def bubble_sort_length(array):
n = len(array)
swapped = True
while swapped and n >= 0:
swapped = False
for i in range(0, n-1):
if len(array[i]) > len(array[i+1]):
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
swapped = True
n = n - 1
return array
# Main
words = ["elephant", "cat", "giraffe", "dog"]
sorted_words = bubble_sort_length(words)
print("Before sort -", words)
print("After sort -",sorted_words)
def bubble_sort_length(array): # Function to sort words by length
n = len(array) # Store the length of the array
swapped = True # Boolean to control loop
while swapped and n >= 0: # Repeat while swaps happen
swapped = False # Assume no swaps this pass
for i in range(0, n-1): # Loop through array
if len(array[i]) > len(array[i+1]): # Compare word lengths
temp = array[i] # Store first word temporarily
array[i] = array[i+1] # Move second word forward
array[i+1] = temp # Put stored word into second position
swapped = True # Record that a swap happened
n = n - 1 # Reduce sorting range
return array # Return sorted array
# Main
words = ["elephant", "cat", "giraffe", "dog"] # Create array of words
sorted_words = bubble_sort_length(words) # Sort words by length
print("Before sort -", words)
print("After sort -",sorted_words)
Task 4 - Alphabet
Create a program that sorts an array of characters into alphabetical order using bubble sort.
You must compare the characters using ord().
letters = ["d", "a", "c", "b"]
Before sort - ["d", "a", "c", "b"] After sort - ["a", "b", "c", "d"]
# Main words = ["elephant", "cat", "giraffe", "dog"] sorted_words = bubble_sort_length(words) print(sorted_words)
def bubble_sort_characters(array):
n = len(array)
swapped = True
while swapped and n >= 0:
swapped = False
for i in range(0, n-1):
if ord(array[i]) > ord(array[i+1]):
temp = array[i]
array[i] = array[i+1]
array[i+1] = temp
swapped = True
n = n - 1
return array
# Main
letters = ["d", "a", "c", "b"]
print("Before sort -", letters)
sorted_letters = bubble_sort_characters(letters)
print("After sort -", sorted_letters)
def bubble_sort_characters(array): # Function to sort characters alphabetically
n = len(array) # Store the length of the array
swapped = True # Boolean to control loop
while swapped and n >= 0: # Repeat while swaps happen
swapped = False # Assume no swaps this pass
for i in range(0, n-1): # Loop through array
if ord(array[i]) > ord(array[i+1]): # Compare ASCII values
temp = array[i] # Store first character temporarily
array[i] = array[i+1] # Move second character forward
array[i+1] = temp # Put stored character into second position
swapped = True # Record that a swap happened
n = n - 1 # Reduce sorting range
return array # Return sorted array
# Main
letters = ["d", "a", "c", "b"] # Create array of characters
print("Before sort -", letters) # Display unsorted array
sorted_letters = bubble_sort_characters(letters) # Sort characters
print("After sort -", sorted_letters) # Display sorted array
Task 5 - Parallel Array Sort
Create a program that sorts player scores from highest to lowest using bubble sort.
The program must use parallel arrays so that the player names stay matched with their scores.
names = ["Ali", "Ben", "Cara", "Dan"] scores = [45, 78, 62, 91]
Before sort ["Ali", "Ben", "Cara", "Dan"] [45, 78, 62, 91] After sort ["Dan", "Ben", "Cara", "Ali"] [91, 78, 62, 45]
# Main
names = ["Ali", "Ben", "Cara", "Dan"]
scores = [45, 78, 62, 91]
print("Before sort")
print(names)
print(scores)
names, scores = bubble_sort_scores(names, scores)
print("After sort")
print(names)
print(scores)
def bubble_sort_scores(names, scores):
n = len(scores)
swapped = True
while swapped and n >= 0:
swapped = False
for i in range(0, n-1):
if scores[i] < scores[i+1]:
temp = scores[i]
scores[i] = scores[i+1]
scores[i+1] = temp
temp = names[i]
names[i] = names[i+1]
names[i+1] = temp
swapped = True
n = n - 1
return names, scores
# Main
names = ["Ali", "Ben", "Cara", "Dan"]
scores = [45, 78, 62, 91]
print("Before sort")
print(names)
print(scores)
names, scores = bubble_sort_scores(names, scores)
print("After sort")
print(names)
print(scores)
def bubble_sort_scores(names, scores): # Function to sort scores and names
n = len(scores) # Store the length of the array
swapped = True # Boolean to control loop
while swapped and n >= 0: # Repeat while swaps happen
swapped = False # Assume no swaps this pass
for i in range(0, n-1): # Loop through scores
if scores[i] < scores[i+1]: # Compare neighbouring scores
temp = scores[i] # Store first score temporarily
scores[i] = scores[i+1] # Move second score forward
scores[i+1] = temp # Put stored score into second position
temp = names[i] # Store first name temporarily
names[i] = names[i+1] # Move second name forward
names[i+1] = temp # Put stored name into second position
swapped = True # Record that a swap happened
n = n - 1 # Reduce sorting range
return names, scores # Return sorted arrays
# Main
names = ["Ali", "Ben", "Cara", "Dan"] # Create names array
scores = [45, 78, 62, 91] # Create scores array
print("Before sort") # Display unsorted arrays
print(names)
print(scores)
names, scores = bubble_sort_scores(names, scores) # Sort arrays
print("After sort") # Display sorted arrays
print(names)
print(scores)