GCSEComputer ScienceEdexcelRevision Notes1. Computational ThinkingAlgorithmsStandard Sorting Algorithms

Standard Sorting Algorithms (Edexcel GCSE Computer Science)

Revision Note

James Woodhouse

What is a sorting algorithm?

  • Sorting algorithms are precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets

  • Three common sorting algorithms are:

    • Bubble sort

    • Merge sort

Bubble Sort

What is a bubble sort?

  • A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in 'pairs' and swaps them if they are not in the correct order

  • One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple 'passes' to sort the dataset

  • The algorithm is finished when there are no more swaps to make

How do you perform a bubble sort?

Step

Instruction

1

Compare the first two values in the dataset

2

IF they are in the wrong order...

  • Swap them

3

Compare the next two values

4

REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)

5

IF you have made any swaps...

  • REPEAT from the start (pass 2,3,4...)

6

ELSE you have not made any swaps...

  • STOP! the list is in the correct order

Example

  • Perform a bubble sort on the following dataset

5

2

4

1

6

3

Step

Instruction

1

Compare the first two values in the dataset

5

2

4

1

6

3

2

IF they are in the wrong order...

  • Swap them

2

5

4

1

6

3

3

Compare the next two values

2

5

4

1

6

3

4

REPEAT step 2 & 3 until you reach the end of the dataset

  • 5 & 4 SWAP!

2

4

5

1

6

3

  • 5 & 1 SWAP!

2

4

1

5

6

3

  • 5 & 6 NO SWAP!

2

4

1

5

6

3

  • 6 & 3 SWAP!

2

4

1

5

3

6

  • End of pass 1

5

IF you have made any swaps...

  • REPEAT from the start

  • End of pass 2 (swaps made)

2

1

4

3

5

6

  • End of pass 3 (swaps made)

1

2

3

4

5

6

  • End of pass 4 (no swaps)

1

2

3

4

5

6

6

ELSE you have not made any swaps...

  • STOP! the list is in the correct order

Examiner Tip

In the exam, you do not have to show every swap that takes place in a bubble sort. You can show the outcome of a bubble sort at the end of each pass. If you have the outcome of each pass correct then a bubble sort has been implemented correctly and all marks will be given!

A bubble sort in python

  • In the exam, students are required to understand the mechanics of the algorithm as well as the advantages and disadvantages of it

  • Students are not required to remember the code for the algorithm

# unsorted dataset
nums=[66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]

# count the length of the dataset
numlength = len(nums)

# sets a flag to initiate the loop
swaps = True

while swaps == True : 
    swaps = False
    # loop through the dataset
    for y in range(numlength-1) :
        # if the first number is bigger than the second number
        if nums[y] > nums[y+1] :
            # swap the numbers using a temporary variable
            temp = nums[y]
            nums[y] = nums[y+1]
            nums[y+1] = temp
            # sets the flag to true
            swaps = True

# prints the sorted list
print (nums)

Worked Example

A program uses a file to store a list of words.

A sample of this data is shown

Milk

Eggs

Bananas

Cheese

Potatoes

Grapes

Show the stages of a bubble sort when applied to data shown  [2]

How to answer this question

  • We need to sort the values in to alphabetical order from A-Z

  • You CAN use the first letter of each word to simplify the process

Answer

  • E, B, C, M, G, P (pass 1)

  • B, C, E, G, M, P (pass 2)

Merge Sort

What is a merge sort?

  • A merge sort is a sorting algorithm that uses the 'divide and conquer' strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order

How do you perform a merge sort?

Step

Instruction

1

Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)

2

Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)

3

REPEAT step 2 until all sub-datasets are merged together into one dataset

Example

  • Perform a merge sort on the following dataset

7

4

1

2

6

3

8

5

Step

Instruction

1

Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)

7

4

1

2

6

3

8

5


divide in half (2 datasets of 4 values)

7

4

1

2

 

6

3

8

5


divide in half again (4 datasets of 2 values)

7

4

 

1

2

 

6

3

 

8

5


divide in half again  (8 datasets of 1 value)

7

 

4

 

1

 

2

 

6

 

3

 

8

 

5

2

Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)

7

 

4

 

1

 

2

 

6

 

3

 

8

 

5


Merge into 4 datasets of 2 values

4

7

 

1

2

 

3

6

 

5

8

3

REPEAT step 2 until all sub-datasets are merged together into one dataset

Merge into 2 datasets of 4 values

1

2

4

7

 

3

5

6

8


Merge into 1 dataset of 8 values (in the correct order)

1

2

3

4

5

6

7

8

Examiner Tip

In the exam, the divide stage could already be done for you and you would only need to demonstrate the conquer stage!

  • The code for a merge sort is complex and not necessary for the exam

  • In the exam students are only expected to be able to follow the steps and illustrate the algorithm, not code it

Last updated:

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Next topic

    Did this page help you?

    James Woodhouse

    Author: James Woodhouse

    Expertise: Computer Science

    James graduated from the University of Sunderland with a degree in ICT and Computing education. He has over 14 years of experience both teaching and leading in Computer Science, specialising in teaching GCSE and A-level. James has held various leadership roles, including Head of Computer Science and coordinator positions for Key Stage 3 and Key Stage 4. James has a keen interest in networking security and technologies aimed at preventing security breaches.

    Lucy Kirkham

    Author: Lucy Kirkham

    Expertise: Head of STEM

    Lucy has been a passionate Maths teacher for over 12 years, teaching maths across the UK and abroad helping to engage, interest and develop confidence in the subject at all levels.Working as a Head of Department and then Director of Maths, Lucy has advised schools and academy trusts in both Scotland and the East Midlands, where her role was to support and coach teachers to improve Maths teaching for all.