Searching & Sorting Lesson Notes

searching.md

Searching

Objectives

• Write pseudocode for linear search
• Write pseudocode for binary search
• Translate algorithm pseudocode to working code
• Describe the Big O complexity of linear and binary search

Guiding Questions

• Take a minute to look over these examples of pseudocode for a selectEvenNumbers function. Which one do you prefer? Why?

  Style 1:

  function selectEvenNumbers takes 1 parameter, numbers (array of integers)
  
  create evenNumbers variable and set to an empty array
  
  for each num in numbers array
    check if num is even
      add num to evenNumers array
  
  return evenNumbers
  

  Style 2:

  Function selectEvenNumbers
    Input: numbers -> array integers
    Output: array of integers
  
  set evenNumbers -> []
  
  for i = 0 to i = numbers.length
    if (numbers[i] % 2 === 0)
      push numbers[i] onto evenNumbers
  
  return evenNumbers
  

  Linear Search

  Given an array of integers, numbers, and a value val, a linearSearch() function should return the index of val in numbers. If val does not exist in numbers, return -1.

  Your answer...

• What is the Big O complexity of Linear Search?

  Your answer...

• How does binary search work in your own words. What condition needs to be met to use binary search on an array?

  Your answer...

• Write pseudocode for Binary Search. Start by forking this: https://repl.it/@galvanize/BinarySearch

  Your answer...

• Translate your pseudocode from above to working code.

  Your answer...

• What is the Big O complexity of Binary Search?

  Your answer...

Resources

• Pseudocoding / problem solving: https://www.techinasia.com/talk/10-steps-solve-programming-problem
• Binary Search:
  • https://www.geeksforgeeks.org/binary-search/
  • https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

sorting.md

Sorting

Objectives

• Write pseudocode for Selection Sort
• Write working code for Selection Sort
• Describe the Big O complexity of Selection Sort
• Write pseudocode for Merge Sort
• Write working code for Merge Sort
• Describe the Big O complexity of Merge Sort

Guiding Questions

• Write pseudocode for Selection Sort.

  Your answer...

• Translate pseudocode into working code for Selection Sort.

  Your answer...

• What is the Big O complexity of Selection Sort.

  Your answer...

• Write pseudocode for Merge Sort. Start from this example: https://repl.it/@galvanize/MergeSort

  Your answer...

• Translate pseudocode into working code for Merge Sort.

  Your answer...

• What is the Big O complexity of Merge Sort.

  Your answer...

Resources

• Algorithm visualizations:
  • https://visualgo.net/en
  • https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  • https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/
• Merge sort in JS: https://hackernoon.com/programming-with-js-merge-sort-deb677b777c0
• Merge sort folk dance: https://www.youtube.com/watch?v=XaqR3G_NVoo