Sometimes, there is no point in reinventing methods of solving problems. There are a number of 'standard algorithms' which can be adapted to suite all variety of different problems. In this section, we look at standard sorting and searching algorithms.
We are learning ...
So that we can ...
Visualization and Comparison of Sorting Algorithms (4:25) Apologies for the horrible sound track ...
Click to engage A bubble sort (or sinking sort) is so called because the 'lighter' items in an unordered list of values 'bubble' to one end of the list whilst the 'heavier' items 'bubble' to the other. As you can see from the animation, the effect of this algorithm is to find the largest item and move it up to the top of the list. After every pass, there is no need to check the largest item again because it's always in the right place. AlgoRhythmics Bubble Sort (5:16) - Follow one dancer at a time Task 1.1 Playing card bubble sort Where you simulate a bubble sort using playing cards Get one suit of 13 playing cards - from 'Ace' to 'King'. What the ordered list should look like Shuffle the suit and lay them face down in a line on the desk in front of you. Eek! The list is unordered - but where are the cards? Follow the algorithm carefully to bubble sort the cards into ascending order. Don't cheat - you are only allowed to look at two cards at a time or else you'll spoil the magic. Your teacher will demonstrate this to you as well. Bubble Sort Algorithm There are two ways of doing this - by doing something until a condition is true ...
... or doing something while a condition is true ...
... it doesn't really matter which you choose - the outcome is the same. Try following either of these algorithms really carefully. You might want to ask your shoulder partner to give you the instructions whilst you carry them out. When you have finished, turn over all the cards and be amazed! They are in ascending order! Task 1.2 Pseudocode bubble sort Where we learn how to represent a bubble sort using pseudocode You will (probably) need to remember the pseudocode version for your exam! Nightmare! Copy the pseudocode algorithm below by hand into your notebooks / on paper. In this algorithm ...
Note that the FOR loop runs from 0 through n-2 because the list indices start at 0 and run to n-1 and we ignore the last item anyway so we have to stop at n-2. This always causes confusion!SET swap ← trueWHILE swap = true SET swap ← false FOR i ← 0 TO n - 2 IF sequence[i] > sequence[i + 1] THEN SET temp ← sequence[i] SET sequence[i] ← sequence[i + 1] SET sequence[i + 1] ← temp SET swap ← true END IF NEXT i SET n ← n - 1END WHILEYou can perform a bubble sort with a repeat ... until loop but Python doesn't have one 😢Use your favourite search engine to look for a 'bubble sort flowchart' - look carefully at the ones you have found and compare them to the algorithm above. When you have found one which looks the same or similar, print a copy out for your folders - remember to write your name on it and make sure it's got a suitable title. Watch the animation carefully. It shows an example of a bubble sort using the algorithm you have learnt. Bubble sort step by step (click to advance the animation) On paper, use a bubble sort algorithm to rearrange the following unordered list into ascending order, showing the list of numbers after each "pass". For each pass, state the number of comparisons you have made and the number of swaps you have made. To make this task easier, you could use playing cards or numbers on pieces of paper. 7,2,5,9,3 Consider laying out your work in a trace table like this (I've done the first one for you) ... In your notebooks or on paper, answer the following questions in full sentences ...
Task 1.3 Python bubble sort Where we learn how to implement a bubble sort using Python Of course, there is little point talking about Bubble sort unless we can implement it in Python! Let's go ... Open up the Python programming environment and create a new, blank script. Save this in a suitable place in your documents and give it a suitable filename (for instance, bubbleSort.py).Carefully type in the following *unfinished* code into the script. import random# Titleprint('Bubble sort')# Generate a random sequence of 16 integerssequence = random.sample(range(100),16)# Print out unordered sequence print('Unordered :',sequence) # Start bubble sort # Finish bubble sort# Print out the ordered sequenceprint('Ordered :',sequence)Use the pseudocode algorithm in Task 2.2 to complete the Python script between the comments! Don't give up if it doesn't work first time - you will probably type in the pseudocode expecting it to run, but it won't, however, the pseudocode is very similar to the Python code ... so ... When you run the script (by choosing 'Run > Run Module' or pressing 'F5') you should get something like ... Print the script out in colour using Notepad++, write your name on the printout and annotate the script to explain how it works. Hand it into your teacher for assessment.
Click to engage An insertion sort looks at each item in the unordered list and works back through the list to insert it in its rightful place. When you find its place, you insert it and start to work with the next item in the unsorted portion of the list until you have worked all the way through the list. AlgoRhythmics Insertion Sort (4:04) Task 2.1 Playing card insertion sort Where we learn how to simulate an insertion sort using playing cards Get one suit of 13 playing cards - from 'Ace' to 'King'. What the ordered list should look like Shuffle the suit and lay them face down in a line on the desk in front of you. What? The list is unordered again - but how do I get them back in order? Follow the algorithm carefully to insertion sort the cards into ascending order. Don't cheat - you are only allowed to look at two cards at a time or else you'll spoil the magic. Your teacher will demonstrate this to you as well. Insertion Sort Algorithm
When you have finished, turn over all the cards and be amazed! They are in ascending order! Task 2.2 Pseudocode insertion sort Where we learn how to represent an insertion sort using pseudocode You will need to remember the pseudocode version for your exam! Super nightmare! Copy the pseudocode algorithm below by hand into your notebooks / on paper. In this algorithm ...
Using the Boolean sentinel is one way of implementing this algorithm. There are simpler ways but this is the safest. SET item ← sequence[i] SET current ← i - 1 SET placed ← false WHILE (current >= 0) AND NOT placed SET sequence[current + 1] ← sequence[current] SET current ← current - 1END IF END WHILE SET sequence[current + 1] ← item NEXT iUse your favourite search engine to look for a 'insertion sort flowchart' - look carefully at the ones you have found and compare them to the algorithm above. When you have found one which looks the same or similar, print a copy out for your folders - remember to write your name on it and make sure it's got a suitable title. ... in the amazing Flowgorithm ... Watch the animation carefully. It shows an example of a insertion sort using the algorithm you have learnt. I have used the same short list of numbers from the bubble sort so you can compare them more easily. Insertion sort step by step (click to advance the animation) On paper, use an insertion sort algorithm to rearrange the following unordered list into ascending order, showing the list of numbers after each "pass". For each pass, state the number of comparisons you have made and the number of swaps you have made. To make this task easier, you could use playing cards or numbers on pieces of paper. 7,2,5,9,3 Consider laying out your work in a trace table like this (I've done the first one for you) ... In your notebooks or on paper, answer the following questions in full sentences ...
Task 2.3 Python insertion sort Where we learn how to implement an insertion sort using Python Again, there is little point knowing the theory if we can't implement the algorithm in Python! Let's go ... Open up the Python programming environment and create a new, blank script. Save this in a suitable place in your documents and give it a suitable filename (probably ' insertionSort.py').Carefully type in the following *unfinished* code into the script. import random# Print titleprint('Insertion sort')# Generate a random sequence of 16 integerssequence = random.sample(range(100),16)# Print out unordered sequenceprint('Unordered :',sequence)# Start insertion sort# End insertion sort# Print out the ordered sequenceprint('Ordered :',sequence)Use the pseudocode algorithm in Task 3.2 to help you to complete the Python code between the comments. Remember that the algorithm is not written in Python - you have to convert it into Python for it to work. When you run the script (by choosing 'Run > Run Module' or pressing 'F5') you should get something like ... Use Notepad++ (or equivalent) to print out your script in colour. Make sure you put your name on it and annotate the script to explain how it works. Hand it in to your teacher for assessment.
Click to engage Merge sort is a funny algorithm to study at this level because it uses a technique called recursion which you wouldn't really learn until Stage 5, so I'm not going to expect you to understand the mechanics of the pseudocode version or certainly to implement a Python version of it. A merge sort is in a class of algorithms known as divide and conquer because it relies on decomposing a larger problem into smaller ones until each smaller problem is trivial to solve. It relies on breaking a list of 'n' items into 'n' single-item, ordered (!) sequences and then merging the sequences back together again, choosing the correct value from the available sublists. The animation above may make it clearer or you might want to have a little dance ... AlgoRhythmics Merge Sort (4:17) Task 3.1 Playing card merge sort Where we learn how to simulate a merge sort using playing cards Get one suit of 13 playing cards - from 'Ace' to 'King'. Ah, yes - an ordered list of cards Shuffle the suit and lay them face up in a line on the desk in front of you. At least I can see where the cards are now! Your deck won't be the same as mine though ... Follow the algorithm carefully to merge sort the cards into ascending order. It's important that you can see the cards this time - it will make the algorithm easier to follow. Your teacher will demonstrate this to you as well. Merge Sort Algorithm
When you have finished, turn over all the cards and be amazed! They are in ascending order! Task 3.2 Tracing the operation of a merge sort Where we learn how to trace the operation of a merge sort The merge sort uses a technique called recursion which is well suited to problems like this. Since recursion can be a little tricky to get your head around, we'll not cover this as a programming technique in detail until Stage 5. We will trace the operation of the merge sort in a different way than the bubble or insertion sorts but still we will keep track of the stages and operations like we did before. In your notebooks / on paper As the merge sort uses a recursive algorithm, the pseudocode version would require some quite advanced techniques. It's enough, at this stage to recall the 'structured English' version. Copy the following into your notebooks / onto paper by hand. Split the unordered list in half into two sublistsUNTIL the length of each sublist is oneWHILE there are still unmerged sublists CHOOSE a pair of sublists FOR each value in both sublists CHOOSE the next lowest value and place it in a new sublistWatch the animation below carefully. You should clearly see the two stages in the merge sort. Merge sort step by step (click to advance the animation) Using a suitable diagram on paper, describe the stages in the merge sort of the following unordered sequences. For each step in each sequence, make a note of the number of operations including splitting the original sequences and comparing and assigning items in the subsequence to the new sequence. 5,8,7,1,2,6,3,4 4,6,3,7,5,1,2 1,5,4,2,6,3 Hand in your diagrams to your teacher for assessment. Make sure your thinking is clear.
There is no cut and dried answer to 'which sorting algorithm should I use'. I totally depends on both the size and the initial state of the unordered sequence ...
Why would you think that? Task 4.1 Worksheet Where we complete a worksheet comparing sorting algorithms Download a copy of the Comparing sorting algorithms worksheet and save this in a suitable place in your documents. You will have to print out the worksheet before you complete it. If you haven't got access to the algorithms for the three sorting methods, you can download Sorting algorithms handout - a handy reference :) You will need to focus on the basic operations of all sorting algorithms ...
The simplest type of search simply looks through a sequence of values one-at-a-time until either the item is found or the end of the list of reached. As you can imagine, this is very inefficient for large sets of data. However, it will work with unordered data sets which is useful in some situations CS50 Linear search (2:50) Task 5.1 Following a linear search algorithm Where we learn how to follow a linear search algorithm As we have seen, the linear search algorithm is only really suited to sequences which are unordered. An unordered sequence of names Working with your shoulder partner, describe the algorithm verbally. Get your shoulder partner to write down your explanation whilst you are doing this. Then read through the algorithm - does it make sense? Refine and share. Look carefully at the following algorithm for a linear search. It presumes an unordered list of integer values called sequence. Read it out loud to your shoulder partner and compare it to the process described in the video. INPUT targetSET match ← FalseSET index ← 0WHILE match = False AND index <= length(sequence)-1 IF sequence[index] = target THEN SET match ← True ELSE SET index ← index + 1 END IFIF match = True THEN OUTPUT 'Item Found'ELSE OUTPUT 'Item not found'END IF Copy the pseudocode algorithm by hand into your notebooks / on to paper. Watch the clever lion ... Click the lion to load a scratch implementation of a linear search. Lion chooses a random number and then searches for it in an unordered list of numbers. He's not very clever though, so he has to follow the steps in the algorithm ... Click Lion to watch him perform a linear search Download a flowchart of the algorithm made using Flowgorithm. You should attempt to construct the flowchart yourself - ask your teacher if you get stuck. Task 5.2 Linear search in Python Where we learn how to implement a linear search in Python So, ready to implement this yourself? Again, I'm not really going to give you much help with this! Open up the Python programming environment and create a blank script, save it in a suitable place with a suitable filename (like ' linearSearch.py' for instance).Carefully type the following *unfinished* Python code into the script. Correct, it's not finished ... import random# Print titleprint('Linear search')# Generate random sequence of 20 integerssequence = random.sample(range(100),20)# Print unordered sequenceprint('Sequence :',sequence)# Start linear search# End linear searchUse the pseudocode algorithm from Task 6.1 to implement a Python linear search between the comments. Don't just type in the pseudocode commands - they are not Python (but they are not a million miles away!) When you run the completed script, it should produce output something like this for an item in the sequence ... 15 comparisons are required to find the number 38 ... or like this for an item not in the sequence ... 20 comparisons are required to find that the number 14 is NOT in the list! Use Notepad++ to print out your attempt at this challenge. Remember to write your name on it and annotate the script to explain what it is doing. Hand it in to your teacher for assessment
Binary search is an example of a divide and conquer algorithm. The sequence must be sorted in order for this algorithm to work correctly. Watch the video ... CS50 Binary search (9:31) Task 6.1 Following a binary search algorithm Where we learn how to follow the progress of a binary search algorithm. As you have seen, the binary search algorithm relies on the sequence being ordered. An ordered sequence of names Working with your shoulder partner, explain how a Binary search works. Get your partner to write down your instructions carefully. Read back over what has been written - does it make sense? Rewrite, share! Look carefully at the algorithm for a binary search. Read the algorithm aloud to your shoulder partner and compare it to the procedure described in the video and also your response to Step 1 ... INPUT targetSET start ← 0SET end ← length(sequence)-1SET middle ← 0SET match ← FalseWHILE (match = False) AND (start <= end) SET middle ← (start + end) DIV 2 IF sequence[middle] = target THEN SET match ← True ELSE IF sequence[middle] < target THEN SET start ← middle + 1 ELSE SET end ← middle - 1 END IFIF match = True THEN OUTPUT 'Item found'ELSE OUTPUT 'Item not found'END IFCopy the pseudocode algorithm by hand into your notebooks / on paper. Watch the clever ducky! Click the ducky to load a scratch implementation of a binary search. Ducky chooses a random number and then searches for it in an ordered list of numbers. He's not very clever though, so he has to follow the steps in the algorithm ... Click ducky to watch him perform a binary search Task 6.2 Binary search in Python Where we learn how to implement a binary search in Python So, ready to implement this yourself? Again, I'm not really going to give you much help with this! Open up the Python programming environment and create a blank script, save it in a suitable place with a suitable filename (like 'binarySearch.py' for instance). Carefully type the following *unfinished* Python code into the script. Correct, it's not finished ... import random# Print titleprint('Binary search')# Generate random sequence of 20 integerssequence = random.sample(range(100),20)sequence.sort() # WHAT! You can sort it like this!!!# Print unordered sequenceprint('Sequence :',sequence)# Start binary search# End binary searchUse the pseudocode algorithm from Task 7.1 to implement a Python binary search between the comments. Don't just type in the pseudocode commands - they are not Python (but they are not a million miles away!) When you run the completed script, it should produce output something like this for an item in the sequence ... Only THREE operations are required in order to find the target is in the list Only FOUR operations are required in order to find the target is NOT in the list Use Notepad++ to print out your attempt at this challenge. Remember to write your name on it and annotate the script to explain what it is doing. Hand it in to your teacher for assessment
Click to load key word list to help you make your own flash cards Quick win - sorting algorithms Quick win - searching algorithms 15 Sorting Algorithms in 6 Minutes Remember, you only need to know Bubble, Insertion and Merge for the exam!
Look back at the video (with the horrible soundtrack) start of the lesson. Investigate how some of the other sorting algorithms demonstrated work. Remember that the merge sort implementation is too complicated for Stage 4. Ask your teacher to show you how to use these structured versions. |
 |
|
|
|
Teachers Resources
Online Safety Links
This website and its contents are licensed under a ...
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License
Chinese Panda Character from GraphicMama Team on Pixabay