This quiz is to assess your learning from the previous lesson. Read the description below and select which term it is referring to:

'The merge sort algorithm has two parts: splitting items and merging items'

The first part of a merge sort it to repeatedly split a list in half until all the elements are in a list by themselves.

Each stage of the merge sort algorithm can be shown in two parts: splitting the items and merging pairs of lists.

The merge sort algorithm is less complex to implement than bubble sort.

The advantage to merge sort is that it requires more memory, often due to the new lists that need to be created.

"Executing a merge sort takes up extra space in memory, as new lists are made each time a list is split or two lists are combined."

"A merge sort algorithm is usually slower to execute but more easier to write than bubble sort."

"Merge sort is an efficient divide and conquer algorithm that can perform well in real-world use."

Merge Sort

﻿Hi, I'm Kashif your computer science teacher for the algorithms unit. In this lesson we're going to be reviewing what you've learned in this unit. For this lesson, you're going to need pen, some paper, and you're going to need to remove any distractions that can get in the way of you focusing. Once you've done that, let's begin. Mystery code. Take a look at the Python code on the left-hand side. We've got some questions based on that. So number one, what algorithm is this? Number two, what is the purpose of the variable I? And number three, how could this algorithm be improved? Write your answers down. So the algorithm here is the linear search. The variable I, the purpose is at the start of the algorithm, we assigned I to the value minus one and that value is an output or returned if the item is not found. So the value one, the value minus one signifies that the search item has not been found. And how could this algorithm be improved? A flag could be used to stop the while loop when an item has been found. So as you saw with the previous examples we would initialise a flag. And then if we find the item, we will set the flag to true and we will stop searching and stop all the comparisons. What does that mean? That we don't keep on comparing once we've got the item that we're looking for. This could improve the algorithms efficiency by reducing the number of comparisons made. In this lesson you will interpret algorithms and suggest improvements, analyse and fix errors in the flow chart and perform searching and sorting algorithms on samples of data. Review lesson. In this lesson, you are going to review and practise different areas of the algorithms topic, including flow charts, searching algorithms and sorting algorithms. Task one- Counting unordered items. Look over the flow chart and answer the questions. Pause the video to complete your task. Task one- Counting own unordered items. Using the worksheet complete task one. Resume once you're finished Counting unordered items-solution. So as we can see what you were given was on the left-hand side, on the right hand side highlighted in yellow are the solutions. So in the first decision box or the if statement there we needed to include the variable count. In the second decision, the operator for comparing. So the comparison operator that was used was less than however what we should be using would have been the greater than. And lastly, instead of unordered equals one because there were just assigning unordered to the value of one. Instead, we need to increment it. And how we do that is by using unordered equals, unordered plus one Task two- Searching and sorting. Complete the tasks on searching and sorting algorithms. Pause the video to complete your task. Task two- Searching and sorting. Using the worksheet complete Task two. There are three parts, song names, merge song and comparing bubble sort and merge sort. Resume once you're finished. Task two- Searching and sorting bubble sort solution. So here we have the solution for the bubble sort. Compare it to what you've got and give it a take if you've got the correct answer if not, make a note of where you can make them improvements. How I normally check my answer for bubble sort, is I check to see after the first pass that the last column has got the highest value or in terms of the letter that's dry towards the end of that fair, which he starts with W. And then on the second pass, the last two are correct. The third pass, the last three are correct and so on. Task two- Searching and sorting merge sort solution. So once again, check the answers give yourself a big take if you've got it right. Well done. If not make note of where you've gone wrong. Task three- Reviewing insertion sort. Eliza has been given a list of trees that are common in the UK and wants to record which ones she can find in the town she lives in. To make this easier, Eliza wants to put the tree species into ascending order first. Practise using the insertion sort. Pause the video to complete your task. Task three- Reviewing insertions sort. Using the worksheet complete task three. Resume once you're finished, Task three- Reviewing insertion sort solution. So as we can see there, we've got our list of items. Our sub list is on the left-hand side in grey and it's sorted and our unsorted sub list with the white background is unsorted. So sorted sub list, unsorted sub list. After the first pass, two items are now in the sorted sub list and they've been inserted in. After the second pass, we could see Birch which was after the first pass, it was the first item in the unsorted sub list is come right to the star of the sorted sub list and as we're going along each time an item's been inserted in. Comparing bubble sort and merge sort. For each phrase, choose whether it refers to bubble sort or merge sort. Splits data repeatedly until each item is in a list of its own. Write your answers down. Do you think that's the bubble sort or do you think that's the merge sort? Okay. So the answer for that was merge sort. Plus where we are breaking down and splitting up the data each time. Next, compares items next to each other in the list and swaps them if they are in the wrong order. Do you think it's bubble sort or merge sort? Write your answers down. So the answer for this was bubble sort. So bubble sort swaps the items until the bubbling all the way to the top and after the first pass we've got the highest item at the end of the list. Next creates a new list. Each time two lists are combined. Write your answers down, bubble sort or merge sort.` That was merge sort. Next is poor at sorting large collections of unordered data bubble saw or merge saw. So the answer there was bubble sort. The reason is because there's going to be lots of swapping going on and there's going to be lots of passes that are taking place. So therefore, because of the constant swaps large collections of unordered data would take a lot of time. Next can be really quick to sort data that is nearly in order. Bubble sort or merge sort. Write answers down. The answer once again is bubble sort. So if it's nearly in order, we're not going to have to do as many swaps. So that's why that's the answer. Next. The algorithm is simpler to write. Write your answers down. So the algorithm does seem to dry is also bubble sort. Next is a divide and conquer algorithm And the answer there was merge sort. Why, because we break it each time and then merging it second time round. comparing bubbles sort and merge sort. An advantage of merge sort over bubble sort is that it's faster to sort large lists and lists that less ordered. Bubble sort can be quicker than merge sort on smaller lists and lists are mostly in order. There is often not a one size fits all answer to sorting data And that's the end of the lesson and the end of the algorithms unit. Thank you very much for joining me on this unit. I hope you've got a better understanding of flow charts trace tables, sorting algorithms, and searching algorithms. If you would like to share your work you can get in contact with us @OakNational and #LearnwithOak Thank you very much for your time and goodbye.

This quiz is to assess your learning from this lesson. Read the description below and select which term it is referring to:

‘Split data until each item is in a list of its own and then combine pairs of lists repeatedly so that the items are in order.’

‘Move through a list repeatedly, comparing items next to each other and swapping them if they are in the wrong order.’

Analyse the flow chart below. Which algorithm does this represent?

What does the initial value of -1 indicate?

Which sort splits data repeatedly until each item is in a list of its own

Which sort  creates a new list each time two lists are combined

An advantage of merge sort over bubble sort is that it is faster to sort large lists and lists that are less ordered.

Bubble sort can be quicker than merge sort on smaller lists and lists that are mostly in order.

Algorithms Review

In this lesson, we will practise and cement our knowledge of what we they have learnt in the algorithms unit. The worksheets contain a range of questions on flow charts, searching algorithms, and sorting algorithms that will help prepare us for the summative assessment for the unit.

Lesson overview:Algorithms review

Core Content

Algorithms: