Searching and Sorting Algorithms

• What is a key feature of a bubble sort?

  Uses an outer while loop
• What type of search is a linear search also known as?

  Sequential search
• What is the main drawback of a linear search for large lists?

  It is not very efficient
• What is a key feature of a binary search?

  It requires a sorted list
• How does a bubble sort determine when to stop?

  Stops when no swaps are made
• How does a binary search find the target value?

  By comparing the midpoint to the target
• What is the concept behind merge sort?

  Divide and conquer
• How does merge sort combine the data?

  Combines items in the correct order
• What does a bubble sort compare?

  Adjacent data elements
• When does an insertion sort stop?

  When all elements are sorted
• What is a key feature of a linear search?

  Uses a loop to check each value
• What happens if a match is not found in a linear search?

  The value is not included
• What are the key features of a binary search?

  Calculates midpoint, lowpoint, and highpoint
• What does a merge sort do recursively?

  Splits sublists into left and right
• What is a key feature of an insertion sort?

  Uses an outer for loop
• How does an insertion sort find the correct position?

  Moves backwards in the sorted part
• What are the steps to find the number 8 using a linear search in the list 12, 5, 3, 2, 8, 19, 14, 6?

  1. Start at the first element (12).
  2. Check if 12 equals 8 (no).
  3. Move to the next element (5).
  4. Check if 5 equals 8 (no).
  5. Continue checking each element until 8 is found.
• How would you find the number 2 using a binary search in the list 1, 2, 3, 4, 5, 6, 7, 8, 9, 10?

  1. Calculate the midpoint (5).
  2. Compare midpoint (5) to target (2).
  3. Since 2 is less, ignore upper half.
  4. New list: 1, 2, 3, 4.
  5. Repeat until 2 is found.
• Explain how a merge sort would sort the list 4, 8, 5, 1, 3, 6, 7, 2.

  1. Split the list into halves repeatedly.
  2. Continue until each item is separate.
  3. Merge sublists back together in order.
  4. Resulting sorted list: 1, 2, 3, 4, 5, 6, 7, 8.
• Describe how a bubble sort would sort the list 3, 1, 6, 5, 2, 4.

  1. Compare 3 and 1, swap.
  2. Compare 3 and 6, no swap.
  3. Continue comparing and swapping.
  4. Repeat until no swaps are made.
  5. Resulting sorted list: 1, 2, 3, 4, 5, 6.
• How would an insertion sort sort the list 5, 2, 6, 3, 1, 4?

  1. Start with the first element (5).
  2. Compare and insert 2 before 5.
  3. Continue inserting each element in order.
  4. Resulting sorted list: 1, 2, 3, 4, 5, 6.
• What are the key features of a linear search?

  • Uses a loop to check each value
  • Increments by 1 for each check
  • Ends if a match is found or list ends
• What are the key features of a binary search?

  • Calculates midpoint, lowpoint, and highpoint
  • Uses a while loop for comparisons
  • Ignores half of the data each iteration
• What are the key features of a merge sort?

  • Recursive algorithm
  • Splits lists until length of 1
  • Merges sublists in correct order
• What are the key features of an insertion sort?

  • Uses an outer for loop
  • Uses an inner while loop for positioning
  • Moves backwards to find correct position