Sorting and Searching Essentials Quiz Quiz

Test your foundational knowledge on sorting algorithms, choosing sort keys, binary search, and two-pointer strategies. This quiz covers the basics of sorting and searching in computer science, helping you reinforce key concepts with clear examples.

1. Array Sorting Key Choice

   When sorting a list of students by their exam scores in descending order, which attribute should you use as the sort key?

   1. Date of birth
   2. Student name
   3. Student ID
   4. Exam score

   Explanation: The correct attribute for sorting students by exam results is their exam score, as it directly reflects the desired order. Sorting by student name or ID would organize the list in ways unrelated to academic performance. Sorting by date of birth is useful for age-based arrangements but irrelevant for exam score lists. Using the right sort key ensures the sorting is meaningful for the task.

2. Binary Search Precondition

   What must be true about a list before you can apply binary search to find a number efficiently?

   1. The list must be of even length
   2. The list must have unique values
   3. The list must be in reverse order
   4. The list must be sorted

   Explanation: Binary search requires the data to be sorted because it works by repeatedly dividing the range in half based on order. Having unique values is not essential, as duplicates do not affect the process. Being in reverse order is only acceptable if you adjust the binary search logic, and even length is not a requirement at all.

3. Two-pointer Technique Scenario

   Which problem is commonly solved efficiently using the two-pointer technique after sorting: finding two numbers in an array that add up to a target value?

   1. No, only for unsorted arrays
   2. Yes, but only for duplicate values
   3. Yes, it is commonly used
   4. No, sorting is not required

   Explanation: The two-pointer approach is effective for finding pairs with a specific sum after sorting an array, allowing you to move pointers inward based on the sum. Sorting is usually required for this strategy to work efficiently. The technique is not limited to duplicate values or unsorted arrays. Suggesting that sorting is not needed misunderstands when the two-pointer method is optimal.

4. Stability in Sorting Algorithms

   Which sorting property ensures that equal elements remain in their original relative order after sorting?

   1. Efficiency
   2. Stability
   3. Complexity
   4. Scalability

   Explanation: Stability ensures that duplicate items retain their initial sequence, which is important for certain applications. Efficiency refers to speed or resource usage, not element position. Complexity describes algorithmic behavior, and scalability relates to handling larger data. Only stability directly addresses relative order preservation among equal items.

5. Effect of Randomly Ordered Data on Sorting

   If a list of numbers is randomly ordered, what is the main benefit of sorting it before performing a binary search?

   1. Enables efficient search
   2. Makes the list shorter
   3. Automatically removes duplicates
   4. Increases randomness

   Explanation: Sorting transforms a random list into an ordered one, which is required for binary search to function efficiently. Sorting does not affect the randomness of data or automatically delete duplicates. The length of the list stays the same, so it does not become shorter.

6. Selecting a Sort Key for Multiple Criteria

   When you want to sort athletes first by their country and then by their finish time, which method should you use to choose the sort keys?

   1. Sort randomly, then by name
   2. Sort by country, then by finish time
   3. Sort by finish time only
   4. Sort by name, then by country

   Explanation: Sorting first by country groups athletes by nation, then sorting by finish time arranges them within those groups by performance. Sorting by finish time only ignores country grouping, while sorting randomly produces no meaningful order. Sorting by name and then by country does not align with the intended goal.

7. Binary Search Comparison Steps

   If you use binary search to find the number 7 in the sorted list [2, 4, 7, 10, 13], what is the first number you compare 7 with?

   1. 2
   2. 7
   3. 13
   4. 10

   Explanation: Binary search begins by comparing the middle element, which is 7 in this list. Although 2 and 13 are the first and last elements, binary search does not start with them. 10 is to the right of the middle and would be compared only if needed. The correct answer is the actual middle value.

8. Best Choice for Sorting Short Lists

   Which basic sorting algorithm is often efficient and easy to implement for very small lists?

   1. Heap sort
   2. Fourier sort
   3. Radix sort
   4. Insertion sort

   Explanation: Insertion sort is simple and fast for sorting small arrays due to its low overhead. Heap sort and radix sort are generally better for larger datasets, and 'Fourier sort' is not a standard sorting algorithm. Thus, insertion sort is the most practical for short lists.

9. Interpreting Search Outcomes

   What does it mean if binary search returns -1 or indicates 'not found' when searching for 20 in the sorted list [1, 3, 6, 12, 15]?

   1. Some elements are duplicated
   2. The list is unsorted
   3. 20 is not in the list
   4. 20 is the last item

   Explanation: A 'not found' result shows the searched element does not exist within the list. Being the last item would require 20 to appear, which it does not. Duplicates or lack of sorting are not necessarily implied by this outcome alone. The correct interpretation is that 20 is missing.

10. Two-pointer Movement After Sorting

    When using the two-pointer technique on a sorted array, how do you typically adjust the pointers if the sum of pointed elements is less than the target?

    1. Move the left pointer right
    2. Move the right pointer right
    3. Move both pointers left
    4. Move both pointers to the ends

    Explanation: If the sum is too small, increasing the lower value by moving the left pointer right helps reach the target. Moving the right pointer right does not make sense as it is already at the high end. Moving both pointers left would decrease the sum, going further from the target if the list is sorted ascending. Moving both to the ends is not necessary unless starting over.