A2 Theory W9 Flashcards
Define the concept of recursion in computer science and explain how it is used in sorting algorithms. Give details about
The basic idea behind recursive sorting algorithms
How they divide the original problem?
How they combine the results.
Give an example of a recursive sorting algorithm and explain how it works.
Recursion is a fundamental concept in computer science that involves a function calling itself in order to solve a problem. It’s a technique where a problem is divided into smaller, similar sub-problems. The base case is a conditional which controls the termination of the recursive function.
Recursive sorting algorithms are sorting algorithms that use the recursive paradigm to sort a list or an array of elements. The basic idea behind these algorithms is to break down the sorting problem into smaller subproblems, sort those subproblems independently, and then combine the sorted subproblems to obtain the final sorted result.
General outline on how recursive sorting algorithms work:
- Divide: the original unsorted list is divided into two or more smaller sublists. This division continues until the sublists are small enough to be considered sorted by definition.
- Conquer: Each smaller sublist is sorted independently. This is typically done using the same sorting algorithm recursively or by applying some base sorting algorithm.
- Combine: Once all the sublists are sorted, they are merged or combined to produce a single sorted list that is the final result
Example: Merge sort
Merge sort is a classic example of a divide and conquer recursive sorting algorithm. It follows the below steps:
- Divide: the unsorted list is divided into two equal or approximately equal halves
- Conquer: Each half is recursively sorted using the merge sort algorithm
- Combine: The two sorted halves are merged into a single sorted list by comparing and merging elements in a way that maintains the sorted order
Briefly describe QuickSort algorithm giving details about
How does it sort a given array?
What is the best and worst case the time complexity of QuickSort and explain why? No explanation no marks.
Does the choice of the pivot matter in a QuickSort algorithm why/why not?
Quick sort is a divide and conquer sorting algorithm. Heres how it sorts a given array:
- choose a pivot element from the array
- partition the array into two subarrays: one with elements less than the pivot and one with elements greater than the pivot
- recursively apply quicksort to the two subarrays
- combine the sorted subarrays and the pivot to obtain the final sorted array
Time complexity:
Best case takes O(n log (n))CompEq time
- always picks median as pivot - where n is the number of elements in the array and CompEq is the cost of comparison
Worst case takes O(n2)CompEq time
- always picks min or max as pivot - where n is the number of elements in the array and CompEq is the cost of comparison
The choice of the pivot matters in Quicksort because it can significantly effect the algorithms performance. A well-chosen pivot that divides the array into nearly equal halves at each step leads to efficient sorting(best-case time complexity) while a poorly chosen pivot that creats unblanced partitions results in worst case time complexity
Briefly describe MergeSort algorithm giving details about
How it sorts a given array?
What is the best and worst case the time complexity of MergeSort and explain why? No explanation no marks.
In which scenario would MergeSort be a good choice of sorting algorithm and explain why.
MergeSort sorts a given array with the following steps:
- divide the input array into equal or approximately equal halves
- continue to divide the arrays into smaller and smaller sections until the base case has been reached
- then recursively sort the subarrays as the merge back together until there are two large halves
- merge the sorted halves into a single sorted array
Time complexity:
Best and worst case are the same: O(n log (n))*CompEq where n is the number of elements in the array and CompEq is the cost of comparison
MergeSort is a good choice of sorting algorithm in scenarios where stability, consistent performance and the use of extra memory is acceptable. It can excel in the following scenarios:
- large datasets: MergeSort has a consistent time complexity for both best and worst case, making it suitable for sorting large datasets efficiently
- stability: MergeSort is a stable sorting algortihm, which means it preserves the relative order of equal elements.
- External sorting: when sorting large datasets that dont fit entirely in memeory, MergeSort can be used for external sorting, where data is sorted in smaller chunks and the sorted chunks are then merged
- predictable performance: unlike QuickSort, MergeSort has a consistent performance regardless of the initial order of elements in the array. This makes it a good choice when you need to guarantee a certain level of performance.
- parallel processing: MergeSort is inherently sutied for parallel, as sorting the two halves can be done in parallel, potentially speeding up the sorting process on multi-core processors
MergeSort does require additonal memory for temporary storage of the two halves during the mergin step, it may not always be the best choice because of this.
Describe the stable and unstable versions of QuickSort and MergeSort. What are the differences between them? Compare the stability of QuickSort and MergeSort and discuss which one would be a better choice in a scenario where stability is important.
Differences between stable and unstable versions:
Quicksort:
- Quicksort is generally considered an unstable sorting algorithm because it doens’t guarantee the relative order of equal elements. The choice of pivots and partitioning can lead to changes in the order of equal elements.
- There is no inherently stable version of QuickSort
MergeSort:
- merge sort is inherently stable because it always preserves the relative order of equal elements during the merging step.
- There is no need for a stable version of MergeSort because it is inherently maintains stability
When stability is important and you need to preserve the relative order of equal elements. MergeSort is a better choice than QuickSort. MergeSort ensures the stability by design, making it suitbale for scenarios where you need to maintain relative order.
Scenarios where you need to maintain relative order:
- Database sorting: When sorting records or data in a database, it’s often essential to keep records with equal keys in their original order to maintain the integrity of the data.
- User interface: In GUI, elemtsn with the same label may need to be sorted while prevering their relative positions
- Sortin objects with multiple criteria: When sorting objects based on multiple criteria, you may need to ensure that the sort is stable to maintain the priority of different criteria
- Grouping data: when grouping data by some criteria and the sorting within each group, stability is crucial to maintain the grouping order
