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)-1
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(sorted_numbers)
def bubble_sort(array):
n = len(array)-1
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(sorted_numbers)
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 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(sorted_numbers) # Display sorted array
3 - Even years
Write a program that will read the data of 10 users from data.txt (name, dob) into an array of records. The program should then display the names of all users born in an even year.
John Smith Michael Brown Daniel Wilson James Anderson William Jackson
John Smith,12/03/2008 Emily Jones,25/07/2007 Michael Brown,18/11/2008 Sarah White,02/05/2007 Daniel Wilson,30/09/2008 Olivia Taylor,14/01/2007 James Anderson,22/06/2008 Sophia Thomas,08/12/2007 William Jackson,17/04/2008 Ava Harris,03/10/2007
| 1 | Read data into array of records | IN | |
| OUT | users(name, dob) | ||
| 2 | Find and display all users born in an even year | IN | users(name, dob) |
| OUT |
2.1 for i from 0 to length of users - 1 2.2 set year to characters 6 to 9 of users[i].dob 2.3 convert year to integer 2.4 if year MOD 2 = 0 then 2.5 display users[i].name 2.6 end if 2.7 end for
# Main users = read_data() display_even_year(users)
from dataclasses import dataclass
@dataclass
class User:
name: str = ""
dob: str = "" # Format: DD/MM/YYYY
def read_data():
users = [User() for i in range(10)]
file = open("data.txt", "r")
for i in range(10):
users[i].name, users[i].dob = file.readline().strip().split(",")
file.close()
return users
def display_even_year(users):
for i in range(len(users)):
year = int(users[i].dob[6:10])
if year % 2 == 0:
print(users[i].name)
# Main
users = read_data()
display_even_year(users)
from dataclasses import dataclass
# Define a record structure to store user details
@dataclass
class User:
name: str = ""
dob: str = "" # Format: DD/MM/YYYY
# Function to read data from file into an array of records
def read_data():
# Create an array of records with 10 empty entries
users = [User() for i in range(10)]
# Open the file for reading
file = open("data.txt", "r")
# Read each line and store values in the array of records
for i in range(10):
# Read line, remove whitespace, split into name and dob
users[i].name, users[i].dob = file.readline().strip().split(",")
# Close the file
file.close()
# Return the array of records
return users
# Function to display names of users born in even years
def display_even_year(users):
# Loop through each record in the array
for i in range(len(users)):
# Extract year from date of birth
year = int(users[i].dob[6:10])
# Check if year is even
if year % 2 == 0:
# Display the user's name
print(users[i].name)
# Main program
# Read data into array of records
users = read_data()
# Display users born in even years
display_even_year(users)