Sorting Algorithms
Introduction
We learn from an early age how to sort things into ordered sets or lists. In early childhood we are given toys like shape sorters to play with which help us to learn categorisation, selection and sorting skills. As we progress we learn the letter alphabet usually in alphabetical order (A..B..C..) and the numerical sequences of natural numbers (0..1..2..3) etc. . So the ability to sort items into a prescribed “standard” or well recognised orders is important both to the individual and to society as a whole.
Practically all professions Scientists, Accountants, Retailers, Teachers (to name but a few) all require data to be sorted and presented in particular orders. As sorting is such an important function and “skill” in society, it is also an important aspect of computer science and is implemented in many of the computer systems that we use day to day. Modern digital computers are very good at doing little things quickly. They are particularly good at adding subtracting and comparing two items at a time, over and over again rather rapidly.
For a computer, comparing two values is a relatively simple task, but what if we need to sort 3, 30, 300, 3,000 or 3,000,000 values? Computer Scientists need to come up with strategies or algorithms that will take a large numbers of unsorted values and re-arrange them into a list of ordered values.
There are in fact may different strategies (or as computer scientists like to call them algorithms) that can be used to sort unordered lists into well ordered lists. Each of these algorithms has its own strengths and weaknesses.
The bubble sort, is a very simple algorithm to understand, but is probably the least efficient way to sort large quantities of values. While the quick sort uses a technique called recursion which is more complex to implement and harder to understand how it works, but is almost universally considered to be the most efficient “general purpose” sort algorithm. Yet other algorithms such as the network sort are ideal for parallel processing environments, but do not work well on a single computer or processor.
In the following sub pages of this article we will be looking at bubble, insert, network and quick sort algorithms.