Sorting algorithms

<< Previous: Searching algorithms Next: Efficiency of algorithms >>

About sorting algorithms

Sorting algorithms are designed to put a list of data in order, either numerical or alphabetical depending on the data.

There are two sorting algorithms you have to be familiar with for your course: the bubble sort algorithm and the merge sort algorithm.

The bubble sort algorithm

The bubble sort works by making pairwise comparisons as it moves through passes of a list until it is sorted. Pairwise comparisons means it starts by comparing the first two items in the list. If they are not in order they get swapped. Then the second and third items are compared. This continues with pairwise comparisons being made until the end of the list is reached.

A full set of pairwise comparisons across the entire list is called a pass of the data. After each pass, the largest number will have bubbled along to the end. This means on each pass you can check one fewer values as the last value will now be correct.

In a very jumbled list we might need to make n-1 passes of the list where n is the number of items in the list. However it may also turn out that it resolves sooner, so a flag should be used to stop making unnecessary comparisons once the list is sorted. If a full pass is made of the data is made and no swaps are made then the data is sorted.

Merge sort algorithm

The merge sort algorithm is a divide and conquer algorithm. It starts by splitting a list in half repeatedly until each sublist is atomic i.e. they contain just one item.

As they are recombined, they are placed in order. First they are put into pairs. Next the pairs are combined, once again putting items in order as they go. This continues until the list is fully recombined.

Comparing the bubble and merge sort algorithms

The merge sort is far more efficient than the bubble sort as far fewer comparisons are made. However, the merge sort requires a large amount of memory in order to function. The merge sort is also considered the more difficult algorithm to program.

Knowledge check

Questions:

Correct:

Question text

<< Previous: Searching algorithms Next: Efficiency of algorithms >>