Topic 1 - Introduction To Algorithms

• Pseudocode keywords:

  • IF
  • ELSE
  • FOR
  • START
  • END
  • CALCULATE (add)
  • INCREMENT (append)  ++ or +=
  • DECREMENT – or -=
  • WHILE
  • INPUT
  • OUTPUT
• Linear Search - Goes in an order
• We start at 0 in a linear search.
• Linear Search - Compares the item you are looking for with the item in that index.
• Linear Search Algorithm

  
  

  Advantages:

  • Does not require the data to be sorted.
  • Could be fast if the search item is towards the beginning of the list.

  Disadvantages:

  • Slow – each item may need to be checked.
• The time complexity for a linear search is O(n).

  
• Binary search - divides the list into half and detects which side is more than or equal to the search term. This process then repeats for the new section of data.
• Binary Search Algorithm

  Advantages:

  • In a worse-case scenario it is quicker.

  Disadvantages:

  • A binary search must be in order.
  • Less space efficient.
• Bubble Sort

  • Compare the first 2 items
  • if they are in the wrong order then swap them
  • continue until there are no swaps available
  • then go through and compare the first two again
  • continue this until all items are sorted and no swaps can be made
• Bubble sort space complexity is O(1)

  
• Bubble sort is slow.
• Bubble sort time complexity is O(n²)

  
• Merge Sort: A sorting algorithm that works by repeatedly swapping adjacent items in a list.
• Merge Sort

  • Splitting an array into half.
  • Then split the approx halved arrays again until all left as 1 in length.
  • Then merge the arrays back by comparing the first items in their arrays.
  • Then continue comparing the first items in the array with the first items in the other halved arrays until all merge back together and hopefully is successfully sorted.
• Merge sort time complexity is O(n*Log n)

  
• Merge Sort

  Advantage:

  • Low time complexity

  Disadvantage:

  • High space complexity