Computational Thinking

1 Algorithms - pattern recognition

Learn It

  • In the previous lesson, we have learned the concept of algorithmic thinking, that is, developing a step by step instructions to solve a problem.
  • Using the sorting quiz score problem from lesson 1, the problem requires you to sort a list of quiz scores from the lowest to the highest.
  • Can you explain why the following solution is not an appropriate algorithm for a computer to carry out?
Look through all the quiz scores
put down the largest one first
then look through the rest of the quiz scores
put down the next largest one after the previous largest one
carry on until all quiz scores are checked
  • Now take a look at the solution below, can you explain what makes this algorithm better?
  • Can you indetify a pattern in it?
  • Can you work out the outcome of the following algorithm? Have the quiz scores sorted?
1. put the list of quiz scores in an array 
2. compare the first score with the second score
3. if the first score is higher
4.       swap its position with the second score in the array
5. Compare the second score with the third score
6. if the second score is higher
7.       swap its position with the third score in the array
8. repeat the above steps until all scores have been compared

Try It - implementing a sorting algorithm

  • Let's try to implement the algorithm above in Python.
  • Here is a list of key Python skills you need:
  • Some steps will be shown to you, but some steps you have to work out yourself. But if you stuck, search online for help or ask your teacher.
  • Open a new file in IDLE or Thorny,
    1. put the list of quiz scores in an array. In Python
      quizScore = [23, 67, 54, 44, 35, 34]
      
    2. compare the first score with the second score
    3. if the first score is higher. The above two steps can be written in Python as one:
      if quizScore[0]>quizScore[1]:
      
    4. swap its position with the second score in the array
      Can you work out how to swap those two's positions?
      
    5. Compare the second score with the third score
    6. if the second score is higher
    7. swap its position with the third score
    8. repeat the above steps until all scores have been compared

Badge It - Silver

  • Finish the implementation so that all quiz scores have been compared and upload a screenshot of your code
  • To help you with picturing what the algorithm does, here is an animation of sorting a list of numbers using the same algorithm.

bubbleSortPassOne.gif

Badge It - Gold

  • Test your Python implmentation and explain why the whole quiz score is not sorted.
  • Upload screenshots of your test and written explaination

Badge It - Platinum

  • Implementing a complete solution so that all the quiz scores have been sorted from the lowest to the highest.
  • Screenshot your code and testing result and upload to www.bournetolearn.com

Author: X Ellis

Emacs 25.1.1 (Org mode 8.2.10)