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 studyA range of resources on algorithms from the CAS community.   YOUTUBE RESOURCE: Continued video lecture taking concept of linear search of a phone book with a binary search algorithm. Takes student to practicing use at home. Posted by New Ways to Learn Ltd.   LEARNING RESOURCE: An 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 studyComputational 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.    YOUTUBE RESOURCE: Introduction to, and analysis of, sequential search algorithms. Video goes on to look at searching with hints. Posted by New Ways to Learn Ltd.  TEACHING RESOURCE: Short blog on the Microsoft Education Blogger site introducing the reasons why students need to learn algorithms. Posted by New Ways to Learn Ltd. Resources for use with pupils Digital Schoolhouse sorting algorithms with Scratch Sorting Algorithms Animation Sorting Algorithms (fun activities by CS Unplugged)Searching Algorithms (fun activities by CS Unplugged)YOUTUBE RESOURCE: Higher-level intro to binary search algorithms, looking at application for number searches in lists such as a phone book. Posted by New Ways to Learn Ltd.AlgoRhythmics has posted a series of sorts performed by Hungarian Folk dancers on YouTube.