Sorting Algorithms

The Bubble Sort is a simple algorithm for ordering the values within an array. However, while it maybe simple, it is not as efficent as other algorithms unless the array it is being applies to meets specific conditions.

Here are the steps the algorithm takes:

• Take the first two values in the array
  • Compare them (if value 1 is greater (>) than value 2)
  • If Value 1 is greater than value 2 - Swap them
  • Else If Value 1 is less than value 2 - Do nothing
• Move into the next pair
• Repeat until there are no more pairs to compare
• Go back to the first two values in the array
• Continue to repeat until you can go through the array without re-ordering any values

The number of passes required increase significantly with the number of items in the array. If the values are in reverse order (which is the worse case scenario) it would take n^2 comparisons. If you had 10 values in reverse order it would take 100 comparisons.

A merge sort breaks down an array into smaller arrays and these smaller arrays are merged in pairs until it is rebuilt into order.

Firstly the array needs to be broken down into individual values. The values are then paired into arrays, and ordered correctly in these new arrays. These arrays are then paired and their values are placed into the correct order. This process is repeated until all the numbers are in order within one array.

Merge sort is more efficent than a bubble sort when used on larger arrays, however the process is not as simple as with a bubble sort.

Insertion sort progressively sorts an array one value at a time to a new array until it is in order.

Here are the steps the algorithm follows:

1. Ignore the first value in the array (this should be moved over to the new array) and go straight to the second value.
2. Select the next value in the origianl array.
3. Place it in the correct place in the new array
4. Move onto the next value (three, four, five… and so on)
5. Repeat step 2 until the whole array is in order

Insertion sort is less efficient with larger lists than merge sort but more efficient than bubble sort. Insertion sort is more memory efficent than bubble sort and merge sort.