Year 10 Searching and Sorting

Algorithms- The Big Picture

Every computer device you have ever used, from your school computers to your calculator, has been using algorithms to tell it how to do whatever it was doing. Algorithms are a very important topic in Computer Science because they help software developers create efficient and error free programs. The most important thing to remember about algorithms is that there can be many different algorithms for the same problem, but some are much better than others!

What makes an Algorithm!

Sequence → Selection → Iteration

Sequencing is the technique of deciding the order instructions are executed to produce the correct result.

Selection is the technique of allowing the algorithm to select which instructions to execute depending on criteria.

Iteration allows an algorithm to repeat instructions. In its simplest form we might specify the exact number of times.

For more explanation https://csfieldguide.org.nz/en/chapters/algorithms/what-makes-an-algorithm/

Task 1 - Write the Algorithm

The following are a bunch of different algorithms for searching and sorting through a list. For each break it down into steps and then draw a flow diagram. You can draw it on paper and then import it into the document if that is easier.

Each of the sections also have a number of questions that need to be answered as well.

Linear Search versus Binary Search

Linear Search

Try the interactive (click the image)

How many guesses do you need?

What do you notice about it? What if there was twice as many boxes?

Binary Search

Try the interactive (click the image)

Now the data is sorted, can you work out a smart way to do it in the least number of guesses?

What would be the best case? What would be worst? What would be the average if you were to do it 100 times?

Sorting

So now we know that it's much faster to search in data that is already sorted, but how do we quickly sort data?

This video looks at 3 increasingly smarter sorting algorithm- bubble sort, insertion sort and quicksort.

Selection SORT versus QuickSort

Selection Sort

Try the interactive (click the image)

Perform the selection sort algorithm on the interactive (or with cards in class).

What do you notice about the algorithm?

How many comparisons did you have to make to be sure the data is sorted?

Quicksort

Try the interactive (click the image)

Try to learn and perform the quicksort algorithm.

How does it compare to the selection sort?

Why do you think it is more efficient?

ASSESSMENT

SEARCHING & SORTING QUIZ

(Teachers insert a link to your copy of "Searching and Sorting EOT Test" form)

FURTHER RESOURCES

Full online textbook https://csfieldguide.org.nz/en/chapters/algorithms/

Bubble-sort with Hungarian ("Csángó") folk dance

AlgoRythmics

15 Different ways to sort data visualised in a few minutes

University of Canterbury Unplugged activity comparing algorithms

The friendship algorithm. Not relevant but really funny!

Intro to big-O notation

Big-O notation is the language we use for talking about how long an algorithm takes to run (time complexity) or how much memory is used by an algorithm (space complexity). Big-O notation can express the best, worst, and average-case running time of an algorithm.

Exact Instructions

Think you can explain something so clearly that even a dumb computer can understand it?

Think again!

If you haven't seen this video check it out.

Computational thinking for digital technologies

At the end of this topic students will have had the opportunity to cover;

understand that there can be more than one algorithm for the same problem PO3
debug simple algorithms and programs by identifying when things go wrong with their instructions and correcting them PO4
be able to explain why things went wrong and how they fixed them PO4
evaluate the efficiency of algorithms PO4
recognise that computers need to search and sort large amounts of data PO4