Year 10 Searching and Sorting

Programming

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!

In this unit, you'll explore some common algorithms for searching and sorting data.

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 - Explore the different Algorithms

One of the most common ways that we can use to explore algorithms is by looking at Searching and Sorting. You can probably already sort a list of numbers, but what steps are you taking exactly? Could you write those steps out so clearly that even a robot could follow them?

The document to the right will guide you through an exploration of different searching and sorting algorithms.

You can use the interactives shown below to follow the algorithm, or you can use a few playing cards.

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?

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?

⬇️ EoT SEARCHING & SORTING ASSESSMENT ⬇️

Complete the SEARCHING & SORTING QUIZ

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!

TED-Ed Cool short video on 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.

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.

LINKS TO NZ CURRICULUM

Digital Technologies | Progress Outcomes

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

Page updated

Report abuse