Sorting Algorithms (Edexcel A Level Further Maths): Revision Note

Introduction to Sorting Algorithms

• Sorting algorithms arrange items (usually values, letters or words) into ascending or descending order

  • whilst arranging a (small) list of items is easy for a human being, machines, robots and computers, etc would need programming to do so

  • as a list of items becomes larger, it becomes increasingly difficult for a human to sort

    • programming a computer to use a sorting algorithm makes the process both accurate and efficient (first time!)

• With sorting algorithms in particular, it is important to stay in 'robot mode'

  • do not be tempted to take shortcuts or miss parts of the algorithm out because the answer can be 'seen'

  • follow each step of the algorithm precisely, in order, exactly as a robot would

Bubble Sort

What is the bubble sort algorithm?

• The bubble sort algorithm arranges items into either ascending or descending order

  • Items are usually values

    • but could be letters or words and similar

    • for questions given in context values will be measures such as weights, lengths, scores or times

How does the bubble sort algorithm work?

• Bubble sort works by comparing pairs of items on the working list

  • the first item is compared to the second, the second to the third, and so on

  • a swap occurs if a pair of items are not in order

    • a pair of equal items would not count as a swap

• This comparison of pairs and possible swaps continues until the end of the working list is reached

  • this is called a pass

  • several passes are usually required to order a list of items 

• At the end of each pass, the item at the end of the working list is in the correct place

  • for ascending order, the highest value 'bubbles' to the top

• Bubble sort, for  items, is complete when either

  • a pass involves with no swaps, or,

  • after the pass

    • i.e.  when only one item would remain on the working list

      • so comparisons are neither possible nor necessary

What is the working list?

• The working list is the list of items that a pass of the bubble sort algorithm will apply to

  • For the first pass every item on the list is in the working list

• After the first pass, the final item is in the correct place

  • other items may be too but the algorithm ensures the highest (for an ascending list) or smallest (for descending) item is at the end of the list

  • this item need not be involved in further comparisons and so it is removed from the working list

• After the second pass, the last two items will be in the correct place

  • After the third pass, the last three items will be correctly sorted, and so on

  • Reducing the working list by one after each pass helps keep the bubble sort efficient as possible by not requiring unnecessary comparisons

• For a list of  items

  • the first pass will have  items on the working list

  • the second pass will have  items on the working list

  • the third pass will have  items on the working list

  • (if required) the  pass will have 2 items on the working list

• Alongside the working list for unordered items, the ordered items may be referred to as the sorted list

• The image below shows a list at the end of the second pass of an ascending bubble sort

  • two items are on the sorted list (12 and 15)

  • the 10 being in the correct position is irrelevant at this stage ('robot mode'!)

  • the third pass will confirm its position and that's when it will become part of the sorted list

How do I work out the (maximum) number of passes in the bubble sort algorithm?

• For a list of  items

  • the maximum number of passes will be 

    • this is because after the  pass, items will be in order, so the last remaining item must be in order too 

    • without actually carrying out a few passes it is hard to predict or work out how many passes bubble sort will need

      • but it may be possible to tell how many more passes are required when only a few items are out of order

  • If the item at the end of the list should be at the start then will take  passes

    • This is because this item will only move one space closer to the start after each pass

How do I work out the (maximum) number of comparisons in the bubble sort algorithm?

• For a list of  items

  • the number of comparisons at each pass will always be one less than the number of items on the working list

    • the first pass will have  items are on the working list so there will be comparisons

    • the second pass will have comparisons

    • the  pass will have  comparisons

    • (if required) the pass will have 1 comparison

  • the maximum number of comparisons for the entire bubble sort algorithm would be

or

• understanding the logic for the number of comparisons is easier than trying to remember a formula

  • the final formula, is quadratic and so bubble sort is of quadratic order

How do I work out the (maximum) number of swaps in the bubble sort algorithm?

• For a list of  items

  • the maximum number of swaps in a pass would be the same as the number of comparisons for that pass

    • i.e. every comparison results in a swap being made

    • this would occur if the first item on the working list is the largest (or smallest for descending)

      • so the maximum number of swaps for the entire algorithm would be needed to if a list started in reverse order

    • with a small working list it is possible to 'see' or count the number of swaps required for a pass

      • it can be awkward keeping track in longer lists so be wary of relying on this sort of inspection technique

      • keeping a tally of swaps as you perform a pass would be more reliable

Quick Sort

What is the quick sort algorithm?

• The quick sort algorithm arranges items into either ascending or descending order

  • Items are usually values

    • but could be letters or words and similar

    • for questions given in context values will be measures such as weights, lengths, scores or times

How does the quick sort algorithm work?

• Each pass of the quick sort algorithm works by splitting a sub-list of the items into two halves around a pivot

  • one half will be the sub-list of values that are less than the pivot

    • for ascending order this sub-list would come before the pivot

  • the other half will be the sub-list of values that are greater than the pivot

    • for ascending order this sub-list would come after the pivot

  • values that are equal to the pivot can be listed in either half

    • for consistency we suggest always listing items equal to the pivot in the half greater than the pivot

  • on both sides of the pivot values would be listed in the order they appeared in the original list

• The quick sort algorithm is complete when every item on the (original) list has been designated as a pivot

Which item is the pivot in the quick sort algorithm?

• The pivot is the middle value in a sub-list of the items, without reordering

  • If there are two items in the middle of a sub-list then either item can be taken as the pivot

    • for consistency we suggest always choosing the item in the upper position as the pivot

• In the first pass, there will be one pivot - the middle item in the whole list

• In the second pass, there could be two (new) pivots - one in the lower half/sub-list, one in the upper half/sub-list

  • The only time this would not be the case is when the pivot is the lowest (ascending) or greatest (descending) item on a sub-list

  • The number of pivots could double at each pass

How do I apply the quick sort algorithm?

• The following list of steps describe the quick sort algorithm for arranging a list of items into ascending order

  • Arranging into descending order would be the same, but the 'ordering' in Step 2 would be reversed

• STEP 1 Find and highlight the pivot (middle value) for each sub-list of items For the first pass only, the sub-list will be the same as the entire list of items 

• STEP 2 List items lower than the pivot, in the order they appear, before the pivot, creating a new (smaller) sub-list Then write the pivot as the next number on the list List items greater than or equal to the pivot, in the order they appear, after the pivot, creating another new (smaller) sub-list

• STEP 3 Repeat steps 1 and 2 until every item on the original list has been designated a pivot The original (full) list of items will now be in ascending order