Insertion Sort
Insertion sort is a simple sorting algorithm that builds a sorted section of the list one item at a time. It takes each value in turn and inserts it into the correct position within the already sorted part of the list.
It is called “insertion sort” because each new value is inserted into its appropriate place among the values that have already been sorted. As the algorithm progresses, the sorted portion of the list grows until the entire list is in order.
def insertion_sort(array):
for i in range(1, len(array)):
value = array[i]
index = i
while index > 0 and value < array[index-1]:
array[index] = array[index-1]
index = index -1
array[index] = value
return array
def insertion_sort(array):
# Traverse the unsorted section of the array
for i in range(1, len(array)):
# Store the current value so it is not overwritten
value = array[i]
# Begin comparing from the current position
index = i
# Continue while:
# - We have not reached the start of the array
# - The value being inserted is smaller than the item to its left
while index > 0 and value < array[index - 1]:
# Shift the larger value one position to the right
array[index] = array[index - 1]
# Move left to continue checking
index = index - 1
# Insert the value into the gap created
array[index] = value
# Return the sorted array
return array
- Select the next unsorted item
- Store the value temporarily
- Compare it with the item to its left
- Shift larger items one position to the right
- Insert the value into the correct position
- Repeat until the entire list is sorted
PROCEDURE insertion_sort(list)
DECLARE value INITIALLY 0
DECLARE index INITIALLY 0
FOR i = 1 to length(list)-1 DO
SET value TO list[i]
SET index TO i
WHILE (index > 0) AND (value < list[index-1]) DO
SET list[index+1] TO list[index]
SET index TO index - 1
END WHILE
SET list[index] TO value
END FOR
END PROCEDURE
Task 1 - Array Ascending
Create a program that sorts the following array into ascending order using insertion sort.
numbers = [7, 3, 9, 1, 5]
Before sort - [7, 3, 9, 1, 5] After sort - [1, 3, 5, 7, 9]
# Main
numbers = [7, 3, 9, 1, 5]
sorted_numbers = insertion_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
# Insertion Sort
def insertion_sort(array):
for i in range(1, len(array)):
value = array[i]
index = i
while index > 0 and value < array[index-1]:
array[index] = array[index-1]
index = index - 1
array[index] = value
return array
# Main
numbers = [8, 4, 2, 9, 1]
sorted_numbers = insertion_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
# Insertion Sort
def insertion_sort(array):
# Loop through the array starting from the second element
for i in range(1, len(array)):
# Store the current value to be inserted
value = array[i]
# Keep track of the current position
index = i
# Move left while:
# - we have not reached the start of the array
# - the value is smaller than the item to its left
while index > 0 and value < array[index-1]:
# Shift the larger value one position to the right
array[index] = array[index-1]
# Move to the next position on the left
index = index - 1
# Insert the value into its correct position
array[index] = value
# Return the sorted array
return array
# Main
numbers = [8, 4, 2, 9, 1]
# Sort the array using insertion sort
sorted_numbers = insertion_sort(numbers)
# Display the original array (now sorted because insertion sort works in-place)
print("Before sort -", numbers)
# Display the sorted array
print("After sort -", sorted_numbers)
Task 2 - Array Descending
Create a program that sorts the following array into descending order using insertion sort.
numbers = [7, 3, 9, 1, 5]
Before sort - [7, 3, 9, 1, 5] After sort - [9, 7, 5, 3, 1]
# Main
numbers = [7, 3, 9, 1, 5]
sorted_numbers = insertion_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
# Insertion Sort
def insertion_sort(array):
for i in range(1, len(array)):
value = array[i]
index = i
while index > 0 and value > array[index-1]:
array[index] = array[index-1]
index = index - 1
array[index] = value
return array
# Main
numbers = [8, 4, 2, 9, 1]
sorted_numbers = insertion_sort(numbers)
print("Before sort -", numbers)
print("After sort -", sorted_numbers)
# Insertion Sort (Descending)
def insertion_sort(array):
# Loop through the array starting from the second element
for i in range(1, len(array)):
# Store the current value to be inserted
value = array[i]
# Keep track of the current position
index = i
# Move left while:
# - we have not reached the start of the array
# - the value is larger than the item to its left
while index > 0 and value > array[index-1]:
# Shift the smaller value one position to the right
array[index] = array[index-1]
# Move to the next position on the left
index = index - 1
# Insert the value into its correct position
array[index] = value
# Return the sorted array
return array
# Main
numbers = [8, 4, 2, 9, 1]
# Sort the array using insertion sort
sorted_numbers = insertion_sort(numbers)
# Display the original array (now sorted because insertion sort works in-place)
print("Before sort -", numbers)
# Display the sorted array
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 = insertion_sort_length(words)
print("Before sort -", words)
print("After sort -", sorted_words)
def insertion_sort_length(array):
for i in range(1, len(array)):
value = array[i]
index = i
while index > 0 and len(value) < len(array[index-1]):
array[index] = array[index-1]
index = index - 1
array[index] = value
return array
# Main
words = ["elephant", "cat", "giraffe", "dog"]
sorted_words = insertion_sort_length(words)
print("Before sort -", words)
print("After sort -", sorted_words)
# Insertion Sort by Word Length
def insertion_sort_length(array):
# Loop through the array starting from the second word
for i in range(1, len(array)):
# Store the current word to be inserted
value = array[i]
# Keep track of the current position
index = i
# Move left while:
# - we have not reached the start of the array
# - the current word is shorter than the word to its left
while index > 0 and len(value) < len(array[index-1]):
# Shift the longer word one position to the right
array[index] = array[index-1]
# Move to the next position on the left
index = index - 1
# Insert the word into its correct position
array[index] = value
# Return the sorted array
return array
# Main
words = ["elephant", "cat", "giraffe", "dog"]
# Sort the words by length
sorted_words = insertion_sort_length(words)
# Display the original array (now sorted because insertion sort works in-place)
print("Before sort -", words)
# Display the sorted array
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
letters = ["d", "a", "c", "b"]
print("Before sort -", letters)
sorted_letters = insertion_sort_characters(letters)
print("After sort -", sorted_letters)
def insertion_sort_characters(array):
for i in range(1, len(array)):
value = array[i]
index = i
while index > 0 and ord(value) < ord(array[index-1]):
array[index] = array[index-1]
index = index - 1
array[index] = value
return array
# Main
letters = ["d", "a", "c", "b"]
print("Before sort -", letters)
sorted_letters = insertion_sort_characters(letters)
print("After sort -", sorted_letters)
# Insertion Sort Characters (Ascending)
def insertion_sort_characters(array):
# Loop through the array starting from the second character
for i in range(1, len(array)):
# Store the current character to be inserted
value = array[i]
# Keep track of the current position
index = i
# Move left while:
# - we have not reached the start of the array
# - the current character comes before the character to its left
while index > 0 and ord(value) < ord(array[index-1]):
# Shift the larger character one position to the right
array[index] = array[index-1]
# Move to the next position on the left
index = index - 1
# Insert the character into its correct position
array[index] = value
# Return the sorted array
return array
# Main
letters = ["d", "a", "c", "b"]
# Display the original array
print("Before sort -", letters)
# Sort the characters alphabetically
sorted_letters = insertion_sort_characters(letters)
# Display the sorted array
print("After sort -", sorted_letters)
Task 5 - Parallel Array Sort
Create a program that sorts player scores from highest to lowest using insertion 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 = insertion_sort_scores(names, scores)
print("After sort")
print(names)
print(scores)
def insertion_sort_scores(names, scores):
for i in range(1, len(scores)):
score_value = scores[i]
name_value = names[i]
index = i
while index > 0 and score_value > scores[index-1]:
scores[index] = scores[index-1]
names[index] = names[index-1]
index = index - 1
scores[index] = score_value
names[index] = name_value
return names, scores
# Main
names = ["Ali", "Ben", "Cara", "Dan"]
scores = [45, 78, 62, 91]
print("Before sort")
print(names)
print(scores)
names, scores = insertion_sort_scores(names, scores)
print("After sort")
print(names)
print(scores)
# Insertion Sort Scores (Descending)
def insertion_sort_scores(names, scores):
# Loop through the scores starting from the second element
for i in range(1, len(scores)):
# Store the current score and matching name
score_value = scores[i]
name_value = names[i]
# Keep track of the current position
index = i
# Move left while:
# - we have not reached the start of the list
# - the current score is larger than the score to its left
while index > 0 and score_value > scores[index-1]:
# Shift the score one position to the right
scores[index] = scores[index-1]
# Shift the matching name one position to the right
names[index] = names[index-1]
# Move to the next position on the left
index = index - 1
# Insert the score and matching name into their correct positions
scores[index] = score_value
names[index] = name_value
# Return the sorted lists
return names, scores
# Main
names = ["Ali", "Ben", "Cara", "Dan"]
scores = [45, 78, 62, 91]
# Display the original lists
print("Before sort")
print(names)
print(scores)
# Sort the scores and names
names, scores = insertion_sort_scores(names, scores)
# Display the sorted lists
print("After sort")
print(names)
print(scores)