2.1 Algorithms

• Abstraction

  obscuring unnecessary detail and picking out important bits of information
• Decomposition

  breaking down of complex problem into smaller problems and solving it individually
• Searching algorithms

  • binary search
  • linear search
• Algorithmic thinking

  a step by step process to solve a problem
• Binary search

  • has to be in order
  • more efficient in larger sets, as it searches through fewer data- more quicker
• Binary search

  1. find middle item
  2. if item found, stop , if item not found yet find middle item till found

  
• Linear search

  • works on unordered list
  • not very efficient on big, long data set
  • simplest search algorithm
• Linear search

  • Example: find elephant in the list:

  [giraffe, antelope, jackal, elephant, lion, deer, cat}

  Giraffe != elephant

  Antelope != elephant

  Jackal != elephant

  Elephant == elephant
• Input/Output Symbol


  A parallelogram-shaped symbol representing data entering or exiting the flowchart, may include Variables and Operators.
• Decision Symbol


  A diamond-shaped symbol representing a condition being evaluated, may include Conditional Statements.
• Process Symbol


  A rectangle-shaped symbol representing a step in the algorithm, may include Actions and Decisions.
• End Symbol


  A circle-shaped symbol representing the end of a flowchart.
• Start Symbol


  A circle-shaped symbol representing the beginning of a flowchart.
• Bubble sort

  • pros

  -works best on small list

  -efficient way to check if a list is in order

  • cons

  -inefficient- doesn’t cope with large list
• Bubble sort

  Example: sort the list=

  66, 21, 38, 15, 89, 49

  1st pass= 21, 38, 15, 66, 49, 89

  2nd pass= 21, 15, 38, 49, 66, 89

  3rd pass= 15 , 12, 38, 49, 66, 89

  1. Look at first two item
  2. If they're in right order it stays as it is, if not swap
  3. Do the step until sorted correctly, smallest to biggest
• Merge sort

  • pros

  - fastest and efficient on larger list
• Merge sort

  1. Make them on their own (split the list)
  2. Merge the into two at first and order them, then merge them all together ordering them from small to big

  
• Insertion sort

  simplest, good with small lists, not good with large list

  uses less memory

  quicker
• Insertion sort

  1. Look at second item
  2. Compare to whole of list and insert in right place
  3. Repeat until sorted

  
• Sorting algorithm

  • Bubble sort
  • Merge sort
  • Insertion sort