Let iqsort(A, 1, n) be an algorithm that sorts an array A with n integers. It wo
ID: 3562726 • Letter: L
Question
Let iqsort(A, 1, n) be an algorithm that sorts an array A with n integers.
It works as follows:
iqsort(A, p, q)
{
if p >= q, return;
r = partition(A, p, q);
// run quick sort on the low part
quicksort(A, p, r - 1);
// run insertion sort on the high part
insertionsort(A, r + 1, q);
}
The psuedo-code for partition(A, p, q) is:
x < A[q]
i < p - 1
for j < p to q - 1
do if A[j] <= x
then i < i + 1
exchange A[i] <> A[j]
exchange A[i + 1] <> A[q]
return i + 1
Compute the best case, worst case, and average case space complexities of iqsort.
Explanation / Answer
Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that
in-place partitioning is used. This requires O(1).
After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.
The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.
Insertion sort is an in-place sorting algorithm, meaning that it requires little to no extra storage. In the case of insertion sort, only a single list element needs to be stored outside of the initial data, making the space complexity O(1).
therefore the total space complexity is
best and average case: O(logn)
worst case: O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.