Merge sort and quicksort exam review
This exam review covers key concepts, techniques, and comparisons of merge sort and quicksort algorithms in computer science, focusing on sorting efficiency and implementation details.
Quiz(32 questions)
1. What type of algorithm is merge sort?
Terms in this Study Set(32)
Flashcards 1(16)
What is merge sort?
A divide-and-conquer algorithm that sorts by dividing the array into halves, sorting each half, and then merging them back together.
How does quicksort work?
Selects a 'pivot' element, partitions the array into elements smaller and larger than the pivot, then recursively sorts the partitions.
True or False: Merge sort is stable.
True - It maintains the relative order of equal elements during sorting.
What is the worst-case time complexity of quicksort?
O(n²) - This occurs when the pivot is the smallest or largest element repeatedly.
Fill in the blank: Merge sort is _____ when dealing with large datasets.
O(n log n) - This is its average and worst-case time complexity.
Comparison: Merge sort vs. Quicksort
- Merge sort is stable - Quicksort is generally faster - Merge sort requires additional space
What is the average-case time complexity of quicksort?
O(n log n) - This efficiency makes quicksort suitable for many practical applications.
What is a pivot in quicksort?
An element chosen to partition the array. It helps in determining the order of elements.
True or False: Merge sort requires additional memory.
True - It requires O(n) additional space for the temporary arrays used during merging.
How do you perform a merge in merge sort?
Combine two sorted arrays into a single sorted array by comparing elements one by one.
What is the best-case time complexity of quicksort?
O(n log n) - This occurs when the pivot divides the array into two equal halves.
Cause → Effect: Choosing a bad pivot in quicksort.
Causes imbalanced partitions → Leads to O(n²) worst-case performance.
What is a base case in merge sort?
An array with one element, which is already sorted and does not require further division.
What does in-place mean in quicksort?
Quicksort sorts elements without requiring extra storage, modifying the input array directly.
How is merge sort implemented?
Recursively split the array, sort each half, and merge sorted results back together.
What is the space complexity of merge sort?
O(n) - This is due to the additional space needed for temporary arrays during merging.
Flashcards 2(16)
Merge sort vs. quicksort: main difference?
Merge sort is stable and divides lists into halves, while quicksort is not stable and partitions around a pivot.
True or False: Quicksort has a worst-case of O(n log n).
False. Quicksort's worst-case time complexity is O(n²) when the pivot selection is poor.
What is the space complexity of merge sort?
Merge sort has a space complexity of O(n) due to the additional arrays used for merging.
Best case scenario for quicksort?
O(n log n), when the pivot divides the array into two equal halves.
Fill in the blank: The primary method of merging in merge sort is ___ .
to combine two sorted arrays into one sorted array.
Which algorithm is generally faster for small datasets?
Quicksort is generally faster due to lower constant factors and better cache performance.
When should you use merge sort?
Use merge sort when stability is required or for large datasets that do not fit in memory.
What is a pivot in quicksort?
A pivot is an element used to partition the array into subarrays for sorting.
True or False: Merge sort can be implemented using recursion.
True. Merge sort is typically implemented using a recursive approach.
Example of a pivot selection strategy?
Random pivot, median-of-three, or first/last element can be used.
How does merge sort handle duplicates?
Merge sort handles duplicates by maintaining their relative order (stable sorting).
What is the average time complexity of merge sort?
O(n log n) consistently, regardless of the input data order.
Cause → Effect: Poor pivot choice in quicksort?
Leads to O(n²) time complexity and inefficient sorting.
Merge sort: divide and conquer strategy explained.
Divide the list into halves, sort each half, then merge them back together.
How does quicksort partition an array?
By rearranging elements so that those less than the pivot come before it and those greater come after.
Which sort is more space-efficient?
Quicksort is more space-efficient, as it requires only O(log n) space for recursion.
Questions in this Study Set(32)
1. What type of algorithm is merge sort?
2. What is the primary characteristic that differentiates merge sort from quicksort?
3. In quicksort, what is the main purpose of the pivot?
4. True or False: Quicksort's average-case time complexity is O(n log n).
5. True or False: Quicksort is always faster than merge sort.
6. What is the space complexity of quicksort in the average case?
7. What is the worst-case time complexity of merge sort?
8. In which scenario is merge sort particularly advantageous?
9. Fill in the blank: The average-case time complexity of quicksort is _____ .
10. What defines a pivot in the context of quicksort?
11. Which of the following statements is NOT true about merge sort?
12. True or False: Merge sort can be implemented both iteratively and recursively.
13. How does quicksort handle an imbalanced partition?
14. What is NOT a common pivot selection strategy in quicksort?
15. What is the best-case time complexity for quicksort?
16. How does merge sort treat duplicate elements during sorting?
17. What does stability mean in sorting algorithms?
18. What is the average case time complexity for merge sort?
19. Which of the following statements about merge sort is true?
20. Cause → Effect: Poor pivot choice in quicksort leads to what outcome?
21. How is merging performed in merge sort?
22. What is the main strategy of the divide-and-conquer approach in merge sort?
23. What is the space complexity of quicksort?
24. How does quicksort rearrange elements during the partitioning process?
25. What happens when you choose the first element as the pivot in a sorted array?
26. Which sorting algorithm is typically more space-efficient?
27. What is a base case in merge sort?
28. When should quicksort be avoided for large datasets?
29. How do you improve the performance of quicksort?
30. What is a practical application of merge sort?
31. Which of the following statements about the average-case time complexity of merge sort is true?
32. Which of the following statements is true regarding quicksort?
Related Study Sets
Informatyka studia – Algorytmy i struktury danych
Hashing Kollisionsauflösung Prüfungsfragen
Minimaler Spannbaum Kruskal Prim Klausurvorbereitung
AVL-Bäume Rotationen Klausurvorbereitung
Sortieren einfach erklärt Karteikarten
Breitensuche und Tiefensuche Definitionen
Heap und Heapsort Karteikarten
Mergesort und Quicksort Laufzeit Definitionen
Create Your Own Study Set
Upload a PDF, paste your notes, or describe a topic – AI generates flashcards, quizzes and more in seconds.
