Sorting Algorithms (Edexcel International AS Maths) : Revision Note

Introduction to Sorting Algorithms

• Sorting algorithms arrange items into ascending or descending order

  • Items that are usually sorted include values, letters or words 

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

  • A computer can be programmed with a sorting algorithm

    • This makes the process both accurate and efficient 

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

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

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

Bubble Sort

What is the bubble sort algorithm?

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

  • Items are usually values

    • They could also be letters or words or 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

  • Comparisons are made working from left to right

  • 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 does not count as a swap

• This comparison of pairs and 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 end

• Bubble sort, for  items, is complete when either

  • a pass involves no swaps, or

  • after the pass

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

What is the working list?

• The working list is the list of unordered 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

  • This item is removed from the working list

  • You may 'see' that other items are in the correct places

    • However, the algorithm ensures the highest (or smallest) item is at the end of the list

• The working list is reduced by one after each pass

  • This keeps the bubble sort as 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

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

• The ordered items may be described 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 

  • The third pass will confirm the position of the 10 and 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 

  • After the pass, items will be in order

    • The last remaining item must be in order too 

  • It is hard to predict how many passes the bubble sort will need

    • 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 it 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 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

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. if 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)

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

    • For a longer list, keep a tally of swaps as you perform a pass 

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

Quick Sort

What is the quick sort algorithm?

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

  • Items are usually values

    • They could be letters or words or 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

    • But for consistency always list items equal to the pivot in the half greater than the pivot

  • On both sides of the pivot, values should be listed in the order they appear in the original list

• The 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

  • For a list containing  items, the pivot will be the th item

    • For consistency round up if necessary

• In the first pass, there will be one pivot

  • This is the middle item in the whole list

• In the second pass, there could be two (new) pivots

  • One pivot in the lower sub-list and one in the upper sub-list

  • The number of pivots could double at each pass

    • But this will not always be the case

    • If a pivot is the lowest or greatest item on a sub-list

How do I apply the quick sort algorithm?

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

  • Arranging into descending order would be the same

    • However, 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
  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

• 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