You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson covers the insertion sort algorithm as required by OCR J277 Section 2.2. Insertion sort is the third standard sorting algorithm you must know for the OCR GCSE Computer Science exam. It is an intuitive algorithm that works similarly to how most people sort playing cards in their hand.
Insertion sort is a sorting algorithm that builds a sorted section of the list one element at a time. It works by taking each element from the unsorted portion and inserting it into its correct position within the sorted portion.
Imagine you are holding a hand of playing cards. You pick up one card at a time and slide it into the correct position among the cards you have already sorted.
procedure insertionSort(list)
for i = 1 to list.length - 1
current = list[i]
j = i - 1
while j >= 0 AND list[j] > current
list[j + 1] = list[j]
j = j - 1
endwhile
list[j + 1] = current
next i
endprocedure
def insertion_sort(lst):
for i in range(1, len(lst)):
current = lst[i]
j = i - 1
while j >= 0 and lst[j] > current:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = current
return lst
numbers = [5, 3, 8, 1, 2]
print(insertion_sort(numbers)) # Output: [1, 2, 3, 5, 8]
OCR Exam Tip: When tracing insertion sort, clearly show which element is being inserted and where it ends up. The examiner wants to see that you understand the element is being placed into its correct position within the already-sorted portion of the list.
Let us sort the list [5, 3, 8, 1, 2]:
Initial list: [5, 3, 8, 1, 2]
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.