|
Part One: Understanding the basicsThe insertion sort is similar to the bubble sort in the fact that it compares adjacent items and swaps them if they are not in order. Where a bubble sort finds the next largest or smallest element an insertion sort takes the element and places it into a "sorted" list at the beginning of the array. The first element in the array is always considered sorted as it is the only element. Then we move onto the second element which we compare to the first. If the second is smaller than the first then we swap the two elements, otherwise we leave them alone. Task 1: Demonstrate your understanding of insertion sort by showing the stages of the sort on the data below. Use this worked example for a step by step work through. |
Part Two: Insertion sort flowchartA flowchart can be used to represent a insertion sort algorithm. It is a useful starting point when beginning to think about how we can code an insertion sort.
Task 2: Hard: Create a flowchart for an insertion sort Medium: Use the outline in the image on the right to complete the flowchart Easier: Use this Lucid Chart file to drag and drop the text into the right places (you will need to make a copy if you want to edit this chart) |
figure 1
figure 2
|
Part Three: Insertion sort Psuedo codeLet's take a look at the key things an insertion sort needs to be able to do:
Figure 1
Line 1: i represents the position of the item that is being checked, i=1 is the first item in the list. The second part of this code means that we only go up to the last but one item in the list, this is because there is nothing to compare the last item in the list to. Figure 2
Line 2: Here we start to implement a for loop that will compare the current item in the list (i) with the item that appears next to it (i+1) |
Part Four: Bubble sort in PythonTask 4a: Using the Psuedo code from task three write a programme that uses a bubble sort to order a list of numbers.
If you are feeling stuck then use the video to the right to help you. Task 4b: As an extension use this CSV file to read, sort, display and write an ordered list (using a bubble sort). |
|
|
Part Five: Bubble sort in ScratchBelieve it or not Scratch is not just a tool used by primary school students! By using Scratch you can apply your knowledge of how a bubble sort works to an interactive environment.
Task 5: Create a simple game that collates a score for each player. Once 3 or more players have played the game use a bubble sort to order the top scores of the players. Task 5b: Make use of cloud variables in order to allow for cloud stored top scores. This will mean that top scores are saved as opposed to forgotten after each session. |