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 .
A 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:
The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
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 notation, divide and conquer algorithms, data structures, randomized algorithms, best, worst and average case analysis, time-space tradeoffs, and upper and lower bounds. (Wikipedia).
Resources for self study
YOUTUBE RESOURCE: Binary Search 3 - Analysis. 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: Searching & Sorting Algorithms. 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 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.
YOUTUBE RESOURCE: Binary Search 1 - Introducing SearchAlgorithms. 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: How many Sorting Algorithms dobeginners need to learn? 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
Sorting Algorithms (fun activities by CS Unplugged)
Searching Algorithms (fun activities by CS Unplugged)
YOUTUBE RESOURCE: Binary Search 2 - The Basic Idea. 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.