Sorting Algorithms

Bubble Sort

Bubble sort is a relatively simple, but inefficient sorting algorithm. Given a list of values, the computer compares adjacent pairs of elements and swaps them if they are not in the right order. It will make several passes of the list until the data is in sorted order.

It’s a very inefficient way of sorting data, as it requires several runs through each list.

The algorithm works as follows:

Step 1:__ __Compare the first two numbers. If the smaller number is on the right, swap these two numbers.

Step 2: Move to the next number in the list and compare these two numbers. If the smaller number is on the right, swap these two numbers.

Step 3:__ __Repeat Step 2 until the last two numbers have been compared. This completes the FIRST PASS.

__Step 4: __SECOND PASS. Repeat steps 1, 2 and 3. No need to compare the last two places.

Step 5:__ __THIRD PASS. Repeat step 1, 2 and 3. No need to compare the last three places.

STOP: When a complete pass produces no swaps.

After the first pass, one number will definitely be in the correct position. Which number is that?
last
Explanation: The last number will always be in the correct place.
After each pass through the data, are there more or less comparisons made?
less
Explanation: On each go, because the previous run put the last number in the correct place, the algorithm doesn't need to check that position.

Sorting Algorithms

A common task that computers need to perform is sorting data into a particular order. There are lots of different methods for doing this, and each one has different advantages and disadvantages. The two main methods we will look at are

  1. Bubble sort
  2. Merge sort

Sorting Algorithms, figure 1

Merge Sort

Merge sort is a recursive algorithm for sorting data. Recursive algorithms are ones that call themselves. When given a list of data to sort, it splits the list in half and sorts each half (using the merge sort algorithm). Then the two halves are merged.

Merge sort is an example of a ‘divide-and-conquer’ algorithm:

  1. Divide (the problem into a small number of pieces)
  2. Conquer (solve each piece, by repeatedly applying divide-and-conquer to it)
  3. Combine (the pieces together into a solution).

We will stick to examples where an even number of elements are sorted. Merge sort starts off by repeatedly splitting (dividing) the array in half until there are only individual elements left. Then pairs of elements are compared and merged into newly sorted lists (conquering).

Each newly sorted list of 2 elements is then merged with another list of 2 elements to create a sorted list of 4 elements, and so on until the final sorted array is reached (combining).

Comparison of the Two

The more complex process used in the merge sort requires fewer steps to complete than the simpler alternative of a bubble sort. However, Merge sort is more difficult to implement because of it’s recursive structure (i.e. it has to call itself). Recursive programming can consume memory as the values need to be stored for each step down the splitting and merging. This means that whilst the merge sort algorithm is more efficient - particularly for large data sets - it can be more memory intensive for a computer.