Search and Sort Algorithms

• What is a linear search?

  A sequential search through a list
• How does a linear search operate?

  It checks each item sequentially
• What happens if the required item is not found in a linear search?

  An error is returned
• When is a linear search appropriate to use?

  When data is not ordered
• What is the efficiency of a linear search?

  Not very efficient
• What is the best case scenario for a linear search?

  Finding the item first
• What is the average number of search steps for 100 items in a linear search?

  50.5 search steps
• What are the steps of a linear search algorithm?

  1. Compare the search item with the first value
  2. Compare with the next value
  3. Repeat until the end or item found
  4. Return the position or -1 if not found
• What is the average case time complexity of a linear search in Big O Notation?

  O(n)
• What is the space complexity of a linear search?

  O(1)
• What is the first step in a linear search algorithm?

  If the list is empty, stop
• What does the Python code for a linear search return if the item is found?

  The index of the item
• What is a binary search?

  A faster search for sorted lists
• What strategy does a binary search use?

  Divide and conquer
• What is the first step in a binary search?

  Select the median item
• What happens if the search item is higher than the median in a binary search?

  Discard the median and lower items
• What is the average number of search steps for a binary search with 100 items?

  Around 6 search steps
• What is the time complexity of a binary search in Big O Notation?

  O(log(n))
• What is the space complexity of a binary search?

  O(1)
• What does the Python code for a binary search return if the item is found?

  The index of the item
• What is a bubble sort?

  A method of sorting data
• How does a bubble sort operate?

  It swaps adjacent items if out of order
• When does a bubble sort complete?

  When a full pass has no swaps
• What is the efficiency of a bubble sort?

  Not very fast
• What is the average case time complexity of a bubble sort in Big O Notation?

  O(n^2)
• What is the space complexity of a bubble sort?

  O(1)
• What are the steps of a bubble sort algorithm?

  1. Compare adjacent items
  2. Swap if out of order
  3. Repeat until no swaps occur
• What is a merge sort?

  A sorting algorithm that splits lists
• How does a merge sort operate?

  It splits lists and merges them sorted
• What is the first step in a merge sort?

  Split the data list into two lists
• What happens to sublists in a merge sort?

  They are recursively split until one item
• What is the average case time complexity of a merge sort in Big O Notation?

  O(n log(n))
• What is the space complexity of a merge sort?

  O(n)
• What does the Python code for a merge sort return?

  A sorted list
• What are the steps of a merge sort algorithm?

  1. Split the list into two halves
  2. Recursively split until one item
  3. Compare first elements of sublists
  4. Select smaller item to merge
  5. Repeat until all sublists are merged
• What is the first step in the Merge Sort process?

  The data list is split into two lists
• How does the Merge Sort continue splitting the lists?

  It recursively splits until each sublist is one item
• What happens after the sublists are split in Merge Sort?

  The first elements of sublists are compared
• What is done with the smaller item in Merge Sort?

  It is selected and written to a new list
• When does the Merge Sort process stop?

  When all sorted sublists are recombined