Home‎ > ‎Key Stage 3‎ > ‎

Algorithms for sorting and searching

Introduction

Pupils should be taught to:
  • understand several key algorithms that reflect computational thinking [for example, ones for sorting and searching]; use logical reasoning to compare the utility of alternative algorithms for the same problem .

sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists. The output must satisfy two conditions:
  1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
  2. The output is a permutation (reordering) of the input.
Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notationdivide and conquer algorithmsdata structuresrandomized algorithmsbest, worst and average case analysis, time-space tradeoffs, and upper and lower bounds. (Wikipedia).

Resources for self study

 

 

  • LEARNING RESOURCE: Searching & Sorting AlgorithmsAn in-depth paper looking at the equations and code behind numerous types of search algorithms, with examples and tasks that can be set. Ideal for revision and consolidation, although rather 'wordy'. Posted by New Ways to Learn Ltd.

Resources for lectures or group study

  • Computational Fairy Tales: over 70 stories introducing computer science concepts by Jeremy Kubica, including 11 stories on algorithms aimed at beginner, intermediate and advanced levels, e.g. The Tortoise, the Hare and 50,000 Ants. 

 

 

Resources for use with pupils

Comments