I am looking for the correct answer to these questions. Please only answer if yo
ID: 3561025 • Letter: I
Question
I am looking for the correct answer to these questions. Please only answer if you actually know them.
1) Describe a case where quicksort will result in quadratic behavior.
2) Give a concise accurate description of a good way for quicksort to improve its performance by using insertion sort.
3) Write two or three clear sentences to describe how a heap sort works.
4) Explain (in English) the algorithm for insertion sort.
5)1) Two of your co-workers (Sam and Kris) both wrote a different unique sorting algorithm. Initial tests (with 50 data elements) show that Kris
Explanation / Answer
1. The quicksort algorithm perform worst i.e., at O(n^2) when all the values of the pivot choosen is either the largest or the smallest of the taken set or considered sublist.
for eg-> 1 2 3 4 5
In this case initially the pivot will be 1 (acc. to quicksort algo). you will have 4 elements on the right side of the pivot and no elements on the left side. Applying this same logic recursively and the pivot chosen is 2, 3, 4, 5 respectively, we have attained a situation where this sort has performed at its worst possible time.
So the quadratic behaviour of QUICKSORT algo is achieved when the list is "Already sorted".
2. Lets assume that you decide on your threshold size to use the insertion sort to be 10, you need to continue recursively split the array by pivot , whenever one of the half's become smaller or equal to 10, you may use the insertion sort that behaves like O(n) on small size arrays.
Take into account that insertion sort will behave badly if your array is sorted reversely (worst case).
As regards to the recursion stuff, you only need to modify the stop case of the quick-sort recursion -> array size <= 10 stop recursion and sort the all the array (which is much smaller in this recursion step) using insertion sort.
By tail recursion , they mean do everything you need with the first half, and then invoke insertion sort for the smaller half as a last method , it is used to save space.
ALGO:
Quick-sort()
choose a pivot
move the smaller elements from left
move the bigger elements from right
quick-sort on the bigger half of the array
if half is less then X
only then do an insertion sort on the other half <- this is a tail recursion insertion sort
else
quick sort on this half also
3. HEAP SORT:
a) Build a Heap 'H' of n number of elements. A heap is basically a binary tree, with an extra property that the larger element is the parent.
b) Repeatedly delete the root element of H. Thus the current largest element will get extracted.
c) Record the result in a reverse array.
d) List will be sorted.
4. Start with the 2nd element of the array as the checkpoint. Compare the checkpoint with the numbers before it, and shift it to the left (as the minimum) of all numbers to the right of it. Increment the checkpoint and repeat the shifting process until the checkpoint reaches the end of the array (and all numbers are sorted).
PSUEDO CODE:
For checkpoint = 1 to array.length
Set minimum to array[checkpoint]
Set shiftpoint to element before checkpoint
While shiftpoint > 0 and array[shiftpoint] > minimum
Set element after shiftpoint to array[shiftpoint]
Decrement shiftpoint
Set A[shiftpoint] to minimum
5. No I will not reject the algorithm of Sam, either for the sake of Kris or else. I will probably test both algorithms for some large data set. An also for the edge cases like:
a) Empty input
b) 1 element input
c) Very long input (maybe of length max(data type used for index))
d) Garbage inside the collection that will be sorted
e) Null input
f) Duplicate elements
g) Collection with all elements equal
h) Odd/even length input
Then, take all these cases and create a long list trying to understand how they overlap. Ex:
a) Empty string case covers the empty collection case
b) Null string == null collection
etc.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.