Lesson video

Hello, my name is Mrs. Holborow, and welcome to Computing.

I'm so pleased you've decided to join me for the lesson today.

In today's lesson, we'll be seeing how searching and sorting algorithms can be represented using flowcharts and performing searching and sorting algorithms on data.

Welcome to today's lesson from the unit, Searching and sorting algorithms. This lesson is called Practising searching and sorting algorithms. And by the end of today's lesson, you'll be able to identify errors in flowcharts representing searching and sorting algorithms. Shall we make a start? Here's a keyword from today's lesson, flowchart.

Flow hart, a diagram that uses symbols to document the logic of an algorithm.

Look out for the key keyword in today's lesson.

Today's lesson is broken down into two parts.

We'll start by analysing and fixing errors in a flowchart, and then we'll move on to perform searching and sorting algorithms on data.

Let's make a start by analysing and fixing errors in a flowchart.

In this lesson, you are going to review and practise different areas of the algorithms topic, including flowcharts, searching algorithms, and sorting algorithms. A flowchart is a diagram used to illustrate the steps of an algorithm.

Flowcharts are made up of symbols, each containing a single step of the algorithm.

The shape of the symbol represents the type of process that the symbol contains.

So an oval or rectangle with curved edges is known as a terminal.

A rectangle represents a process.

Arrows are used as flow lines to show the flow of data or information through the flowchart.

A diamond represents a decision.

This is the only flowchart symbol that will have two flow lines coming out of it.

A parallelogram represents an input or output.

And lastly, a rectangle with two lines inside shows a subprogram.

The purpose of this flowchart is to count the number of pairs of items that are not in the right order.

The order that the items should be in is the lowest to the highest.

Analyse the flowchart and then answer the questions that follow on the next slides.

It might be a good idea to pause the video here and have a careful look at the flowchart.

What is the missing part of the first condition? So in our first decision, what's the missing part? Maybe pause the video whilst you have a think.

That's right, the count variable.

So the first decision should be count < length(items) - 1.

Why is the first condition based on length of items minus 1? Pause the video whilst you have a think.

Did you manage to explain why? Well done.

Each adjacent pair of items needs to be compared, so the number of pairs in a list of items is the total number of items minus 1.

Okay, we are moving on to our first task of today's lesson.

For part 1, there are two errors in the flowchart.

Fix the errors by listing the correct statements.

State the type of error it is and explain your reasoning for each correction.

For part 2, I'd then like you to draw the corrected flowchart.

It may be helpful here to go back to the original flowchart and pause the video whilst you complete the tasks.

How did you get on? Did you manage to spot the errors in the flowchart? Well done.

Let's look at the answers together.

So the first error was is items[count] > items[count] + 1, and this was a logic error.

Based on what the flowchart executes after the true and false scenarios, this condition should be checking if the item after count is smaller than the item at count.

Another fix could be to swap the true and false statements around.

The second error was unordered = unordered + 1.

Again, another logic error.

Setting the value of the unordered to 1 each time that the statement is executed does not record how many pairs of items are out of order.

Instead, unordered should increment by 1 each time there is a pair of items that are not in the correct order.

Let's have a look at the corrected flowchart now.

So here's our corrected flowchart.

So you can see our second decision now says, Is items[count] > items[count] + 1.

And the process underneath that decision is now unordered = unordered + 1, not unordered = 1.

Did you make those corrections in the flowchart? If you didn't quite spot them all, maybe pause the video now and make your corrections.

Okay, so we've analysed and fixed errors in a flowchart.

We are now going to move on to perform searching and sorting algorithms on data.

Whenever there are lots of items, it's important to be able to find the one you need.

For instance, you might need to look through a clothing rail to find an item in your size, or to search through a pack of cards to find a particular card.

Linear search is an algorithm that involves checking each item in a list or sequence of data one at a time to see if it's the right item.

If you have a list that is not in order, a linear search is the only reasonable way to search through it.

So you can see here, this list starts with 4, then 18, 11, and so on.

If we were performing a linear search, we'd start by checking the 4 first, and then we'd move on to the 18, and so on.

The instructions for performing a linear search can be written as, one, take a list of data and an item that is being searched for, the search item.

Two, start from the first item in the list.

Three, compare the item at the current position to the search item.

Four, if it is not the item you are searching for, go to the next item in the list.

Five, if the item at the current position is equal to the search item, then stop searching.

If steps one to five are completed and the search item is not found, then the item is not in the list.

Binary search is an algorithm which can be used to search for an item in a sorted dataset.

It discards half of the remaining data with each comparison and repeats the process until the item is found or until the dataset is exhausted.

On average binary search can locate an item in a list in less time than linear search.

If the data you have is unordered, you must either use a linear search algorithm or sort the data first.

The instructions for performing a binary search can be written as, one, take an ordered list of data and an item that is being searched for, the search item.

Two, maintain a range of items where the search item might be found.

Initially, you set the range to the entire list.

Three, find the item in the middle of the range, the midpoint item.

Four, compare the midpoint item to the item you are searching for.

Five, if the midpoint item is less than the search item, change the range to focus on the items after the midpoint.

Six, if the midpoint item is greater than the search item, change the range to focus on the items before the midpoint.

And lastly, seven, if the item at the midpoint is equal to the search item, then stop searching.

Time to check your understanding.

Which searching algorithm involves checking each item in a list or sequence of data one at a time to see if it's the right item? Is it A, binary search, B, linear search, or C, merge search? Pause the video here whilst you have a think.

Did you select B? Well done.

The linear search algorithm involves checking each item in a list or sequence of data one at a time to see if it's the right item.

Sorting algorithms are used to arrange a sequence of items into a particular order.

This is usually done to make searching faster.

So you can see this original list has now been sorted in ascending order from lowest to highest.

The bubble sort algorithm works by repeatedly going through a list, comparing adjacent items, and swapping the items if they're in the wrong order.

Each time the algorithm goes through the list, it is called a pass.

The pass through the list is repeated until the list is sorted.

The instructions for completing one pass of a bubble sort can be written as, one, take a list of data to be sorted.

Two, go to the next item in the list.

At the start, this will be the first item.

Three, compare the item at the current position to the one next to it.

Four, if the item at the current position is greater than the one next to it, swap the items within the list.

Five, repeat steps two to four until you reach the last item in the list.

It is often much quicker to combine two of items that are already in order together into a new group to help maintain that order.

In computer science, an algorithm called merge sort can be used to combine pairs of sorted lists repeatedly until all the items are in order.

Merge sort splits data until each item is in a list of its own and then combines pairs of lists repeatedly so that the items are in order.

The instructions for performing one merge of a merge sort can be written as, one, take two lists of data to be merged.

Two, create a new empty list for the merged items. Three, repeat steps A to B until one of the lists of items is empty.

A, compare the first items of the two lists.

B, remove the item that is lower and place it into the merged list in the next available position.

Four, then place each item from the remaining list into the merge list in order.

An advantage of merge sort over bubble sort is that is faster to sort large lists and lists that are more unordered.

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

It goes to show that often there is not a one size fits all approach to sorting data.

Time to check your understanding.

For each phrase, choose whether it refers to bubble sort or merge sort.

So the first one, splits data repeatedly until each item is in a list of its own, compares items next to each other in the list and swaps them if they're in the wrong order, creates a new list each time two lists are combined, poor at sorting large collections of unordered data, can be really quick to sort data that is nearly in order, the algorithm is simpler to write, a divide and conquer algorithm.

Pause the video whilst you decide if these statements refer to bubble sort or merge sort.

How did you get on? Did you manage to go through and have a look? Let's look at each answer in turn.

Splits data repeatedly until each item is in the list of its own is merge sort.

Compares items next to each other in the list and swaps them if they're in the wrong order is bubble sort.

Creates a new list each time two lists are combined is a merge sort.

Poor at sorting large collections of unordered data is bubble sort.

Can be really quick to sort data that is nearly in order, bubble sort again.

The algorithm is simpler to write is bubble sort.

And a divide and conquer algorithm is a merge sort.

Okay, we are moving on to our second task of today's lesson, and you've done a fantastic job so far.

So well done.

Alex has been collecting information about popular songs in the U.

K.

during 2019.

Alex now wants to organise the song names in ascending order to make searching for a song easier.

A sample of data is shown in figure 1.

So figure 1 contains the items, Shallow, Location, Sunflower, Giant, Wow.

, Senorita, and Bad guy.

For part 1, can you use linear search to find if a particular song is in the data sample in figure 1? And explain your answer.

For part 2, can you use binary search to find a song in the data sample in figure 1? And again, explain your answer.

Pause the video whilst you answer the questions.

How did you get on? Did you manage to answer the questions? Well done.

Let's have a look at some sample answers together.

For part 1, you were asked whether you could use a linear search to find if a particular song is in the data sample in figure 1.

You can use a linear search to search for a song in the data in figure 1, as a linear search works on both ordered and unordered data.

For part 2, you were asked whether you could use binary search to find a song in the data sample in figure 1.

A binary search cannot be applied to the data in figure 1 as the data must be ordered for a binary search to work.

For part 3, carry out a bubble sort on the data shown in figure 1 by filling in the table below.

Each row should show one pass of the algorithm and any swaps that have been made.

The original data and the first and last pass have been filled in for you.

Pause the video whilst you complete the bubble sort.

How did you get on? Did you manage to complete a bubble sort on the data? Well done.

Let's have a look at the sample answer together.

So we'll on pass 2 because the first pass was done for you.

So pass 2 should be Location, Giant, shallow, Senorita, Bad guy, Sunflower, and Wow.

Pass 3, Giant, Location, Senorita, Bad guy, Shallow, Sunflower, and Wow.

Pass 4, Giant, Location, Bad guy, Senorita, Shallow, Sunflower, Wow.

Can you see what's happening towards the end of our list here? Pass 5, Giant, Bad guy, Location, Senorita, Shallow, Sunflower, and Wow.

And remember, the final pass have been completed for you.

If you need to pause the video here and make any corrections, you can do that now.

For part 4, list the songs that will be compared to the song "Shallow" when performing a binary search on the data from pass 6 in the table on the previous slide.

For part 5, list the songs that will be compared to the song, "I Don't Care," when performing a binary search on the data from pass 6 in the table on the previous slide.

And then for part 6, explain whether a linear search or binary search would be the most suitable algorithm to use when searching for a song from the data in pass 6 of the table on the previous slide.

Pause the video whilst you answer the questions.

How did you get on? Let's look at some sample answers together.

For part 4, you were asked to list the songs that would be compared to the song, "Shallow," when performing a binary search on the data from pass 6 in the table on the previous slide.

So the songs would be "Senorita", "Sunflower", and "Shallow." For part 5, you were asked to list the songs that would be compared to the song, "I Don't Care," when performing a binary search on the data from part 6 in the table on the previous slide.

The songs are "Senorita," "Giant," and "Location." The song, "I Don't Care," doesn't appear in the list.

For part 6, you were asked to explain whether linear search or binary search would be the most suitable algorithm to use when searching for a song from the data in pass 6 on the table on the previous slide, A binary search is usually faster at searching for an item in a list of ordered data than linear search as it halves the number of items to search for with each comparison.

Whilst in the worst case scenario of linear search, every item in the list is compared to the search item.

For part 7, perform a merge sort on the data shown by filling in the table below.

A single row should show each pair of lists that have been merged together.

The first stage of splitting each item into a list of its own has already been done for you.

So we have Giant, Bad guy, Senorita, Location, Sunflower, Wow.

, Shallow.

So these have already been split into their individual lists.

Pause the video whilst you complete the merge sort.

How did you get on? Did you manage to perform a merge sort on the data? Well done.

Let's have a look at the sample answer together.

So the first stage is merging each of the individual items into some paired lists.

So the first one is Bad guy and then Giant.

The second list is Location and then Senorita.

The third list is Sunflower and Wow.

And the fourth list, we only have one item left, so we just copy that down, which is Shallow.

The next stage, we then perform another merge.

So we have a list containing four items, so Bad guy, Giant, Location, and Senorita.

And then the second list contains three items, which are Shallow, Sunflower, and Wow.

And then the final stage is to merge those two lists together.

So we have Bad guy, Giant, Location, Senorita, Shallow, Sunflower, and Wow.

Okay, we've come to the end of today's lesson, Practise searching and sorting algorithms, and you've done a great job.

So well done.

Let's summarise what we've learned together during today's lesson.

Representing searching and sorting algorithms using flowcharts can help you to identify errors.

On average, binary search can locate an item in a list in less time than linear search.

But if the data you have is unordered, you must either use a linear search algorithm or sort the data first.

Sorting algorithms can be used to sort data before a search is completed.

I hope you've enjoyed today's lesson, and I hope you'll join me again soon.

Bye.