Back

Insertion sorting

Introduction
Taking some data such as pupil records from a school and organising them into some kind of order is called 'sorting' the data. You might sort data numerically in ascending order of the primary key, e.g. 2, 6, 8, 12, 14, 17 and so on. You might sort them in descending order, for example 17, 14, 12, 8, 6, 2. You could use a surname to sort the file, in ascending order: Adams, Best, Cartright, Drucker, Egbert and so on, or in a descending order: Egbert, Drucker, Cartright, Best, Adams. The choice of how to organise the data is up to the user and depends on what they want to do with it. The programmer is left with the job of deciding what programming technique to use to sort the data. There are a number of methods that could be chosen.

How does the programmer decide which programming approach to take?
Each sorting method has its own advantages and disadvantages. Whichever method is chosen will decide how long it takes to sort the data and from the user's point of view how long it will take to access sorted data. To select the right method of sorting, the programmer has to ask a number of questions:

• • How much data is there?
  • Can all the data fit into the primary memory at the same time?
  • What kind of device is the data stored on? Tape? The hard drive? CD?

When the programmer knows the answers to these questions, they will be able to select the right method. They might choose an Insertion sort or a Quick sort, for example. There are other methods as well, such as the 'bubble sort'.

Insertion sort algorithm
This is a straightforward algorithm to implement.

• • You take a list of unsorted numbers that you want in ascending order. Unsorted, they start off in position one, position two, position three and so on.
  • Start with the second number in the list (in position two) and compare it to the number in position one.
  • If the number in position two is smaller than the number in position one, insert it in front of the number in position one. Otherwise leave the numbers where they are.
  • Then go to the number in the next position, position three. Find the correct position for the number in position three by first comparing it to the number in position one, and then the number in position two. Insert the number into the correct position if necessary, or leave it in its current position if it does not require moving.
  • Then check the number in the next position, position four. Find the correct place for it by checking it against the numbers in the lower positions in turn; position one first, then position two and finally position three.
  • Continue until all the numbers in the list have been inserted into the correct positions.

An example of insertion sort
Suppose you want to sort these numbers in ascending order: 12, 5, 34, 33, 2, 90, 26