17.6. ALGORITHMS (1.44) – SORTING ALGORITHMS

This is a guide for students attempting the *Algorithms* topic of digital technologies achievement standard 1.44 (AS91074). In order to fully cover the standard, you will also need to have done projects covering the topics of *Programming Languages* and *Human Computer Interaction* in the standard, and included these in your report. ## 17.6.1\. OVERVIEW The topic of *Algorithms* has the following bullet points in achievement standard 1.44, which this guide covers. This guide separates them into two categories. ### 17.6.1.1\. COMPARING ALGORITHMS, PROGRAMS, AND INFORMAL INSTRUCTIONS **Achieved** (A1): “describing the key characteristics, and roles of algorithms, programs and informal instructions” **Merit** (M1): “explaining how algorithms are distinct from related concepts such as programs and informal instructions” **Excellence** (E1): “comparing and contrasting the concepts of algorithms, programs, and informal instructions” ### 17.6.1.2\. DETERMINING THE COST OF ALGORITHMS AND UNDERSTANDING VARIOUS KINDS OF STEPS IN ALGORITHMS **Achieved** (A2): “describing an algorithm for a task, showing understanding of the kinds of steps that can be in an algorithm, and determining the cost of an algorithm for a problem of a particular size” **Merit** (M2): “showing understanding of the way steps in an algorithm for a task can be combined in sequential, conditional, and iterative structures and determining the cost of an iterative algorithm for a problem of size *n*” **Excellence** (E2): “determining and comparing the costs of two different iterative algorithms for the same problem of size *n*” As with all externally assessed Digital Technology reports, you should base your explanations around personalised examples. ## 17.6.2\. READING FROM THE COMPUTER SCIENCE FIELD GUIDE You should read and work through the interactives in the following sections of the CS Field Guide in order to prepare yourself for the assessed project. 2.1 - What’s the bigger picture? 2.3 - Sorting Algorithms Note that 2.2 is not necessary for this project, as 2.2 focuses on *searching* algorithms, whereas this project focuses on *sorting* algorithms. ## 17.6.3\. PROJECT This project involves understanding how selection sort works and the types of steps that can be in it and other algorithms, and then comparing the cost of selection sort and quicksort. ### 17.6.3.1\. WRITING YOUR REPORT FOR THE MAIN BULLET POINTS THAT COVER ALGORITHMS **Achieved** Carry out selection sort on a small amount of data. You can do this either using the balance scale interactive in the field guide (recommended), a physical set of balance scales if your school has them (normal scales that show the exact weights are unsuitable), or as a trace you did using pencil and paper (not recommended). Count how many comparisons you made to sort the items. Take screenshots/ photos of you using the interactive or balance scales to do the sorting. Three or four pictures would be ideal (i.e. one showing the initial state of the scales and weights, one or two in the middle where you are comparing weights, and one at the end where all the weights are sorted). Use a drawing program to draw on each of the pictures and show which weights have been sorted so far, and which have not. Put on the screenshots how many comparisons have been made so far in the sorting process. Write a short explanation of what is happening in the images. Make sure you include the total number of comparisons that was needed to sort the items in your report. Describe (in your own words with a few sentences) the overall process you carried out to sort the weights or numbers. Try and make your explanation general, e.g. if you gave the instructions to somebody who needs to know how to sort 100 numbers, or 500 numbers, the instructions would be meaningful. **Merit** For merit, you need to make it clear that you understand that algorithms can contain iterative, conditional, and sequential steps. If you don’t know what these terms mean, go have another look at the field guide. Get a Scratch program (or another language if you are fairly confident with understanding the language) that implements selection sort. Take a screenshot of it, or a large part of it (you want to ensure that the screenshot takes up no more than half a page in the report, but is still readable) and open it in a drawing program such as paint. Add arrows and notes showing a part of the algorithm that is sequential, part that is conditional, and part that is iterative. Remember that some algorithms are a lot faster than others, especially as the size of the problem gets bigger. It isn’t necessarily the case that if you try to sort twice as many items then it will take twice as long. As a quick warm up investigation to give you some idea of this, try the following. Get an implementation of selection sort (there are some linked to at the end of the chapter in the field guide). Start by choosing a number between 10 and 20\. How many comparisons does it take to sort that many randomly generated numbers with your chosen algorithm? Now, try sorting twice as many numbers. How many comparisons did it take now? Does it take twice as many? Now, try sorting 10 times as many numbers. Does it take 10 times as many comparisons? How many more times the original problem size’s number of comparisons does it actually take? Hopefully you are starting to see a trend here. *If you aren’t attempting excellence,* include the numbers you got from the warm up investigation, along with an explanation of the trend you found. *If you are attempting excellence, you should do the warm up investigation as it will help you (and will only take a few minutes), but you don’t need to write about it.* **Excellence** You probably found in the activity for merit that selection sort isn’t a very good algorithm. So how much better is quicksort? Does the difference become more noticeable as you try to sort more numbers? For your report, you are going to compare selection sort with quicksort. Your objective is to show how much the difference in comparisons between selection sort and quicksort changes as the number of items to be sorted is increased. Choose 10 numbers in the range of 1 to 1000 (you will need a good variety of numbers, some high and some low. Do not pick the same numbers as your classmates!) For each of your 10 numbers, try sorting that many values with each of the sorting algorithms. Record your results in a table that has a column for the problem size, a column for how many comparisons selection sort used, and a column for how many comparisons quicksort used. The best way of visualising the data you have just collected is to make a graph (e.g. using Excel). Your graph should have 2 lines; one for quicksort and one for selection sort, showing how the number of comparisons increases as the size of the problem goes up. Make sure you label the graph well. A simple way of making the graph is to use a scatter plot and put in lines connecting the dots (make sure the data for the graph is increasing order with the smallest problem sizes first and largest last so that the line gets drawn properly). Ask your teacher for guidance if you are having difficulty with excel. Look at your graph. Does the rate of increase for the two algorithms seem to be quite different? Discuss what your graph shows. If you aren’t sure what to include in the discussion of your findings, you could consider the following questions (optional). * What happens to the number of comparisons when you double how many numbers you are sorting with quicksort? What about when you sort 10 times as many numbers? How is this different to when you used selection sort at the start? * What is the largest problem you can solve within a few seconds using selection sort? What about with quicksort? * If you had a database with 1 million people in it and you needed to sort them by age, which of the two algorithms would you choose? Why? What would happen if you chose the other algorithm? ### 17.6.3.2\. WRITING THE PART OF YOUR REPORT THAT ADDRESSES “COMPARING ALGORITHMS/ PROGRAMS/ INFORMAL INSTRUCTIONS” **Achieved/ Merit/ Excellence** We recommend doing this part after you have done programming languages. All three levels (A/M/E) are subsumed by the E requirement, so you should try to do that i.e. “comparing and contrasting the concepts of algorithms, programs, and informal instructions”. You should refer to examples you used in your report or include additional examples (e.g. a program used as an example in the programming languages topic, or an algorithm describing the sorting process, etc). If you are confused, have another look at the field guide. You should only need to write a few sentences to address this requirement. ## 17.6.4\. HINTS FOR SUCCESS * Don’t confuse “algorithm cost” with the “algorithm length”. The number of lines in the algorithm or program normally unrelated to the cost. Cost is the time the algorithm actually takes to run, or the number of comparisons that have to be made. You can find more information in the Field Guide if you are not sure. * While we recommend using the balance scales interactive, if you do include a pen and paper trace, don’t give yourself more than 5 or 6 values to sort, and use an efficient layout that ensures the entire trace takes no more than about half a page. * Resize screenshots/ photos so that they are large enough to see what is on them, but not taking up unnecessary space. * Be sure to label the axis of your graph clearly so that the marker knows what your graph shows. ## 17.6.5\. RECOMMENDED NUMBER OF PAGES Within the 4 pages we recommend for algorithms, a possible breakdown is: * 1 ½ pages: Screenshots and explanations of you carrying out a chosen algorithm and determining the cost of it for your example problem (**Achieved**) * ¼ page: General instructions for carrying out your chosen algorithm (**Achieved**) * ½ page: Example of the iterative, conditional, and sequential steps that can be in an algorithm (**Merit**) * 1 ½ pages: Your investigation and data collected for merit/ excellence. Including results and discussion (**Merit/ Excellence**) * ¼ page: Explanation of the difference between algorithms, programs, and informal instructions (**Achieved/ Merit/ Excellence**) These are *maximums*, not targets! Note that if you go over 4 pages for Algorithms, then you may have to use fewer pages for one of the other two topics, which could be problematic. No other material should be included for Algorithms.