Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array
ID: 3563547 • Letter: L
Question
Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array A with n integers. It works as follows:
ilselect(A, n, i)
{
r=partition(A, 1, n);
//test if A[r] is the element to be selected if i == r, return A[r];
//test if quickselect from the low-part
if i < r, return quickselect(A, 1, r ? 1, i);
//test if linearselect from the high-part
if i > r, return linearselect(A, r + 1, n, i ? r);
}
That is, the algorithm runs quickselect on the low-part or runs linear select on the high-part. Show the worst-case space complexity of the algorithm.
Explanation / Answer
The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.
1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)
Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.
Quicksort works by taking a pivot, then putting all the elements lower than that pivot on one side and all the higher elements on the other; it then recursively sorts the two sub groups in the same way (all the way down until everything is sorted.) Now if you pick the worst pivot each time (the highest or lowest element in the list) you'll only have one group to sort, with everything in that group other than the original pivot that you picked. This in essence gives you n groups that each need to be iterated through n times, hence the O(n^2) complexity.
The most common reason for this occurring is if the pivot is chosen to be the first or last element in the list in the quicksort implementation. For unsorted lists this is just as valid as any other, however for sorted or nearly sorted lists (which occur quite commonly in practice) this is very likely to give you the worst case scenario. This is why all decent implementations take a pivot either randomly or from the centre of the list.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.