Sorting Algorithms - AP Computer Science A

1. Find the primary advantage of using Insertion Sort.

   Efficient for small or nearly sorted arrays. Low overhead and adaptive behavior for special cases.

2. What is the space complexity of Quick Sort with in-place partitioning?

   $O(\text{log } n)$. Recursion depth depends on partition quality.

3. What is the key operation in Selection Sort?

   Selecting the minimum element. Finds the smallest unsorted element and places it correctly.

4. What is the average-case time complexity of Quick Sort?

   $O(n \text{ log } n)$. Good pivot selection typically yields optimal performance.

5. What is the typical use of Counting Sort?

   Sorting integers with a known range. Works when the range of values is small and known.

6. What is the main advantage of Quick Sort over Merge Sort?

   In-place sorting. Quick Sort uses constant space, while Merge Sort needs $O(n)$ space.

7. Find the time complexity of Radix Sort.

   $O(nk)$. Time depends on number of digits $k$ in the largest number.

8. State the space complexity of Merge Sort.

   $O(n)$. Requires additional arrays for the merge operation.

9. What is the primary benefit of using Heap Sort?

   Consistent $O(n \text{ log } n)$ time complexity. Guarantees optimal performance regardless of input distribution.

10. Identify the sorting algorithm that is not comparison-based.

    Radix Sort. Sorts by digit position rather than comparing elements directly.

11. Describe the primary operation of Bubble Sort.

    Repeatedly swapping adjacent elements. Moves larger elements toward the end through adjacent swaps.

12. What is the auxiliary space complexity of Heap Sort?

    $O(1)$. Uses the input array itself as the heap structure.

13. What is the main disadvantage of using Selection Sort?

    Inefficient $O(n^2)$ time complexity. Always performs same number of operations regardless of input.

14. What is the primary disadvantage of using Bubble Sort?

    Inefficiency for large datasets. Quadratic time complexity makes it impractical for large inputs.

15. Which sorting algorithm is often used for educational purposes?

    Bubble Sort. Simple logic makes it ideal for teaching sorting concepts.

16. What is the primary feature of Timsort?

    Hybrid stable sorting algorithm. Combines merge sort stability with insertion sort efficiency.

17. Identify the sorting algorithm used in Python's sorted() function.

    Timsort. Adaptive hybrid algorithm optimized for real-world data.

18. What role does partitioning play in Quick Sort?

    Divides array into two parts for sorting. Separates elements smaller and larger than the pivot.

19. What is the key operation in Heap Sort?

    Building a max-heap and sorting. Creates heap structure then repeatedly extracts the maximum.

20. Find the sorting algorithm with $O(n)$ time complexity for a specific case.

    Counting Sort. Works when input values have a small, known range.

21. Which algorithm is more efficient for small datasets: Insertion Sort or Merge Sort?

    Insertion Sort. Insertion Sort has lower overhead for small arrays.

22. State the stable sorting algorithm suitable for linked lists.

    Merge Sort. Stability and sequential access make it ideal for linked structures.

23. What is the space complexity of Counting Sort?

    $O(k)$, where $k$ is the range of input. Space grows with the range of input values.

24. What is the time complexity of Bubble Sort in the average case?

    $O(n^2)$. Compares each adjacent pair multiple times through nested loops.

25. What is the average-case time complexity of Merge Sort?

    $O(n \text{ log } n)$. Divide and conquer approach ensures consistent logarithmic depth.

26. What is a characteristic of stable sorting algorithms?

    Preserve relative order of equal keys. Equal elements maintain their original relative positions.

27. What time complexity does Selection Sort have in all cases?

    $O(n^2)$. Always performs the same number of comparisons regardless of input.

28. Identify the primary drawback of using Quick Sort.

    Poor worst-case performance. Can degrade to $O(n^2)$ with poor pivot selection.

29. Which sorting algorithm is preferred for external sorting?

    Merge Sort. Sequential access pattern suits external storage devices.

30. State the best-case time complexity of Insertion Sort.

    $O(n)$. Array is already sorted, requiring minimal shifts.

31. Find the best-case time complexity of Bubble Sort.

    $O(n)$. Occurs when array is already sorted, no swaps needed.

32. Which sorting algorithm is typically used in Java's Arrays.sort() for objects?

    Timsort. Hybrid algorithm combining merge sort and insertion sort.

33. Which sorting algorithm is stable: Quick Sort or Merge Sort?

    Merge Sort. Merge Sort preserves relative order of equal elements.

34. What is the worst-case time complexity of Quick Sort?

    $O(n^2)$. Occurs when pivot is always the smallest or largest element.

35. Which sorting algorithm can be easily adapted for singly linked lists?

    Merge Sort. No random access needed, only sequential pointer operations.

36. Which sorting algorithm performs well with nearly sorted data?

    Insertion Sort. Adapts well to existing order, requiring fewer operations.

Study these flashcards