AP Computer Science a Flashcards: Sorting Algorithms

What this deck covers

This deck focuses on Sorting Algorithms, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science a.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: Find the primary advantage of using Insertion Sort.

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

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

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

Flashcard 3: What is the key operation in Selection Sort?

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

Flashcard 4: What is the space complexity of Quick Sort with in-place partitioning?

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

Flashcard 5: Which sorting algorithm is often used for educational purposes?

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

Flashcard 6: What is the time complexity of Bubble Sort in the average case?

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

Flashcard 7: What is the average-case time complexity of Quick Sort?

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

Flashcard 8: What is the typical use of Counting Sort?

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

Flashcard 9: What is the main advantage of Quick Sort over Merge Sort?

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

Flashcard 10: Find the time complexity of Radix Sort.

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

Flashcard 11: State the space complexity of Merge Sort.

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

Flashcard 12: What is the primary benefit of using Heap Sort?

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

Flashcard 13: Identify the sorting algorithm that is not comparison-based.

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

Flashcard 14: Find the primary advantage of using Insertion Sort.

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

Flashcard 15: Find the time complexity of Radix Sort.

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

Flashcard 16: What is the primary feature of Timsort?

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

Flashcard 17: Describe the primary operation of Bubble Sort.

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

Flashcard 18: State the space complexity of Merge Sort.

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

Flashcard 19: Describe the primary operation of Bubble Sort.

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

Flashcard 20: What is the space complexity of Counting Sort?

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

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

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

Flashcard 22: What is the auxiliary space complexity of Heap Sort?

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

Flashcard 23: Find the best-case time complexity of Bubble Sort.

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

Flashcard 24: State the best-case time complexity of Insertion Sort.

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

Flashcard 25: What is the auxiliary space complexity of Heap Sort?

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

Flashcard 26: What is the main disadvantage of using Selection Sort?

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

Flashcard 27: Which sorting algorithm can be easily adapted for singly linked lists?

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

Flashcard 28: What is the primary disadvantage of using Bubble Sort?

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

Flashcard 29: Which sorting algorithm is often used for educational purposes?

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

Flashcard 30: What is the primary feature of Timsort?

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

Flashcard 31: What is the main advantage of Quick Sort over Merge Sort?

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

Flashcard 32: What is the average-case time complexity of Merge Sort?

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

Flashcard 33: Identify the sorting algorithm used in Python's sorted() function.

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

Flashcard 34: What role does partitioning play in Quick Sort?

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

Flashcard 35: Identify the sorting algorithm used in Python's sorted() function.

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

Flashcard 36: What is the key operation in Heap Sort?

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

Flashcard 37: What is the typical use of Counting Sort?

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

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

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

Flashcard 39: Which algorithm is more efficient for small datasets: Insertion Sort or Merge Sort?

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

Flashcard 40: State the stable sorting algorithm suitable for linked lists.

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

Flashcard 41: What is the key operation in Heap Sort?

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

Flashcard 42: What is the space complexity of Counting Sort?

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

Flashcard 43: What is the worst-case time complexity of Quick Sort?

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

Flashcard 44: Which sorting algorithm is stable: Quick Sort or Merge Sort?

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

Flashcard 45: What is the average-case time complexity of Quick Sort?

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

Flashcard 46: What is the primary disadvantage of using Bubble Sort?

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

Flashcard 47: What is the time complexity of Bubble Sort in the average case?

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

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

Answer: Timsort. Hybrid algorithm combining merge sort and insertion sort.

Flashcard 49: What is the average-case time complexity of Merge Sort?

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

Flashcard 50: State the stable sorting algorithm suitable for linked lists.

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

Flashcard 51: What is a characteristic of stable sorting algorithms?

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

Flashcard 52: Which algorithm is more efficient for small datasets: Insertion Sort or Merge Sort?

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

Flashcard 53: What time complexity does Selection Sort have in all cases?

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

Flashcard 54: Identify the primary drawback of using Quick Sort.

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

Flashcard 55: What is the key operation in Selection Sort?

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

Flashcard 56: What role does partitioning play in Quick Sort?

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

Flashcard 57: What time complexity does Selection Sort have in all cases?

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

Flashcard 58: What is the main disadvantage of using Selection Sort?

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

Flashcard 59: Which sorting algorithm is preferred for external sorting?

Answer: Merge Sort. Sequential access pattern suits external storage devices.

Flashcard 60: What is a characteristic of stable sorting algorithms?

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

Flashcard 61: State the best-case time complexity of Insertion Sort.

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

Flashcard 62: Which sorting algorithm performs well with nearly sorted data?

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

Flashcard 63: Find the best-case time complexity of Bubble Sort.

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

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

Answer: Timsort. Hybrid algorithm combining merge sort and insertion sort.

Flashcard 65: Identify the primary drawback of using Quick Sort.

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

Flashcard 66: Which sorting algorithm is stable: Quick Sort or Merge Sort?

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

Flashcard 67: What is the worst-case time complexity of Quick Sort?

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

Flashcard 68: What is the primary benefit of using Heap Sort?

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

Flashcard 69: Which sorting algorithm can be easily adapted for singly linked lists?

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

Flashcard 70: Which sorting algorithm performs well with nearly sorted data?

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

Flashcard 71: Identify the sorting algorithm that is not comparison-based.

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

Flashcard 72: Which sorting algorithm is preferred for external sorting?

Answer: Merge Sort. Sequential access pattern suits external storage devices.