AS

Sorting Algorithms

An algorithm is a sequence of instructions to solve a given problem. Common methods of defining algorithms include pseudo-code, flowcharts and structured English.

Two different types of sort algorithm are bubble sort and insertion sort.

Bubble Sort Algorithm

Works by comparing pairs of numbers in a list and swapping them if one is bigger than the other

The list has to be passed through several times, until the last pass shows no swaps have been made and so the list is in order.

The maximum number of passes that need to happen to ensure the list is in order is n-1, where n= number of items in the list.

You would only use a bubble sort to sort a small list, or for a partially sorted list. It is one of the slowest sorts in existence.

Bubble Sort Algorithm

Procedure BubbleSort

NumberInList = number of items in list

For pass = 1 to NumberInList – 1

Swapped = False

For count = pass to NumberInList

If list(count) > list(count + 1) then

Dummy = list(count)

List(count) = list(count + 1)

List(count + 1) = Dummy

Swapped = true

End If

Next count

If Swapped = False then

End Process

End If

Next pass

End Procedure

See WJEC knowledge organiser for alternative to this algorithm.

Examiner Tips:

Examiners are looking for the following when you write an algorithm.

Declare and initialise variables
Input searchValue
Loop structure and increment
Determine position if found
Output position if found
Correct terminating condition for loop
Output message if not found
Algorithm works as intended.

Insertion Sort Algorithm

How it works: (check out the videos below)

Divide the list into two parts, one item in the sorted part, the rest in the unsorted part.

Bring the next item in the list into the sorted part, then compare with other items in the sorted list to determine where it must go.

Repeat, until all items have been brought into the sorted part and placed in their correct position.

Insertion Sort Algorithm

Declare List(n) as Integer

For position = 1 to LengthOFList

Hole = List(Position) ‘Store the value of the current position in the List into the variable Hole

ListItem = Position ‘Keep shifting all items in the list to the right, whilst the list items are greater than the Hole (and not at end of List)

While ListItem >0 AND List(ListItem – 1) > Hole

List(ListItem) = List(ListItem – 1)

ListItem = ListItem – 1

End While

List(ListItem) = Hole

Next Position

See WJEC knowledge organiser for alternative to this algorithm.

Examiner Tips:

Examiners are looking for the following when you write an algorithm.

Declare and initialise variables
Input searchValue
Loop structure and increment
Determine position if found
Output position if found
Correct terminating condition for loop
Output message if not found
Algorithm works as intended.

Sample Question:

Sample Answer:

This is an algorithm which represents an Insertion Sort.

Always assume anything to the left of the pivot is sorted, even if it’s not.

A pivot item is decided upon, usually the second value in the list.

Loop until the list is sorted

Store the pivot item in memory to create a hole in the list.

Compare each item to the left of the pivot with the pivot item

Insert pivot item into correct place in the list.

Choose next item in the list as pivot

End loop

Compare Bubble Sort with Insertion Sort

How do they both work?

How much quicker is an Insertion Sort, than a Bubble Sort?

How many comparisons does each sorting algorithm need to do?

Test Data

Sort Algorithms - Duplicate values, accending order, decending order, negative numbers

Searching Algorithms - test with value in array, test with value not in the array, dulicate values, test at boundaries

Useful links:

A Bubble Sort can be programmed in a variet of ways.

Find out more here:

https://www.geeksforgeeks.org/bubble-sort-algorithm/

https://www.geeksforgeeks.org/insertion-sort-algorithm/

https://resource.download.wjec.co.uk/vtc/2020-21/ko20-21_1-4/wjec_ko_as_9-4.pdf - WJEC Knowlege organiser.

Page updated

Report abuse