﻿

# Algorithms

There is also a demonstration of algorithms in the new Interactive section.

When you're writing any sort of program in Computer Science, the most important thing is that algorithm - that's effectively the plan, or design, for what your program is going to do. The algorithm should be written in a language-independent form - flowcharts and pseudocode are common forms used for representing an algorithm.

For any task you want to perform with your program, there is sure to be more than one way to do it. With programmming, there isn't necessarily a right or wrong way to do things, but there are efficient and inefficient ways. Which way you go about things will depend on a variety of factors, such as the platform on which the program is to run, and who will be maintaining the code.

If you're writing for an embedded system, for example, or maybe a web-site, you will want to minimise the amount of code you write, or try to reduce the amount of storage required. For a real-time or other time-critical application, you will want to make your code run as quickly as possible. If you're a commercial programmer, and other people are going to be maintaining your code, then you might be better to sacrifice "clever" programming techniques and maybe some performance at run-time in favour of producing easily intelligible functions.

Generally speaking, you will want to maximise the efficiency of your code at run-time. You may want to consider both iterative and recursive solutions, and if you go for the iterative option, your goal will normally be to minimise the number of iterations required to complete the task.

## Searching

A good example to consider when thinking about algorithms is the efficiency of searching. Imagine that someone is thinking of a number from 1 - 100, and you're trying to find out which one it is. You could ask, "Is it 1?", "Is it 2?", "Is it 3?", etc. This is called a linear search. If the person had chosen a number less than ten then you'd be OK, but, on average, you'd need to guess about 50 numbers before you got the right one.

A more effective method is to do what is called a binary search. If your first question is "Is it greater than 50?", then you've ruled out half of the possibilities with one question. That's why it's called a binary search - each question divides the number of possibilities by 2. If, for example, the number chosen was greater than 50, the next question would be "Is it greater than 75?". Using this method, you can find the number in no more than seven guesses.

You can compare the two methods in the Interactive section.

## Sorting

The computing topic in which algorithms and efficiency are most frequently discussed is sorting. There are various sorting algorithms - some are always faster than others, and some are faster than others depending on the numbers being sorted - e.g. whether they're in reverse order, nearly sorted, random, etc. Some are easier to program, and some might be more tricky, so which one you use might depend on how many numbers you need to sort and how critical the performance is.

You can introduce the idea to KS3 Computing students and compare sorting algorithms, using your own numbers, in the Interactive section.

Quite often, when writing a program, you will want to sort some sort of list. I've done this myself on the Lottery page in the JavaScript section of the site. In that particular case there are only six numbers (i.e. performance isn't too great a consideration), so I went with the selection sort as it's easy to program.