AQA GCSE Computer Science - Searching and Sorting Algorithms

Searching Algorithms:

Linear Search:

If I had this array of numbers:

And I wanted to find the number ‘3’, a linear search would work like this:

\

• We look at the first value, in this case, ‘8’
• We assess if this is the required value, in this case, ‘3’
• If this is not the required value, then we move on to the next value. in this case, ‘5’
• We repeat these 3 steps until the value is found, or we come to the end of the array
• Each time we are looking at a new value, this is called a ‘parse’.
  • In this case, 6 parses are needed to find the number ‘3’ with a linear search

\

Binary Search:

If I had this array of numbers:

And I wanted to find the number ‘3’, a binary search would work like this:

\

• Firstly, we need to order the array in ascending order

• We find the middle value of this array by using the formula (n+1)/2, where n is the length of the array, in this case, 7.
  • For this array, we would be looking at the 4th value of ‘5’.
  • If this formula has a result of … .5 add another .5 to this to find the ideal value
• Once we have found the middle value, we need to assess whether this value is higher than, lower than or equal to the required value.
  • If this value is lower than the required value, we remove everything higher than and including this middle value.
  • If this value is higher than the required value, we remove everything lower than and including this middle value.
  • In this case, ‘5’ is higher than ‘3’, so we would remove the upper half of the array like so:

So we are left with:

\

• Next, we use steps 2 and 3 again on this new array
  • In this case, (n+1)/2 would result in us looking at the 2nd value of ‘2’.
• Again, we assess whether the value is higher than, lower than or equal to the required value
  • In this case, ‘2’ is lower than the required value so te 1st and 2nd values would be removed
• We continue this until we reach the required value
• Each time we divide, this is a new parse
  • In this case, 3 parses are needed to find the number ‘3’ with a binary search

\

Linear Search vs. Binary Search

\

Sorting Algorithms:

Bubble Sort:

If I had this array of numbers:

And I wanted to sort this array in ascending order, a bubble sort would work like this:

• We look at the 1st and 2nd values, in this case, ‘8’ and ‘5’
• If the value on the left is larger than the value on the right, we swap these. If not, we keep these how they are.
  • In this case, it would look like this:

• Next, we would look at the 2nd and 3rd values, in this case, ‘8’ and ‘9’.
• Again, if the value on the left is larger than the value on the right, we swap these. If not, we keep these how they are.
  • In this case, it would stay the same
• We continue this for each pair of values in the array.
  • In this case, it would look like this:

• Then again, we do this whole thing again
  • In this case, we would go from this:

To this:

• We keep repeating this until the array is fully ordered.
  • In this case, it would look like this:

• Then we complete one final parse to check that this is fully ordered correctly.
• Each time we sort through the whole array, this is a new parse
  • In this case, 6 parses are needed to sort this array into ascending order using binary search.

\

Merge Sort:

If I had this array of numbers:

And I wanted to sort this array in ascending order, a merge sort would work like this:

• We want to divide this array into 2 parts, of fairly equal length
  • In this case, as there is an odd number, one array shall be slightly longer
  • In this case, this would look like this:

• Then, we want to split these 2 arrays into another further 2
  • In this case, this would look like this:

• We continue this until each value is in its own array
  • In this case, this would look like this:

• Once all the values are separated, we want to merge these back together in ascending order. To do this, we merge each pair back together in ascending order.
  • In this case, this would look like this:

• We want to merge these again back to larger arrays in ascending order. We do not add one array after one another, but we order these whole small arrays.
  • In this case, this would look like this:

• We continue until we finish with one array.
  • In this case, this would look like this:

\

Bubble Sort vs. Merge Sort:

\