Algorithm and data structure question !! Typed is better but not mandotory :) Th

Question

Algorithm and data structure question !!
Typed is better but not mandotory :) Thanks,

What is the complexity of Quicksort algorithm when it is run on the output of an in-order traversal on a binary search tree? You must provide a detailed analysis. (i) ii Consider that we have 100 students each having a unique integer ID between 201800 and 201899. Generate a hash function to store their records in a hash table of 30 slots where the slots are 0, 1, 2, ..., 29. Write another hash function along with a minimum size of the hash table to avoid collision completely

Explanation / Answer

Hi Dear,

Question is long and both question is from different topics.

So, Please post Q 2 in separate post.

I have answered Q1 in details.

First of all: Inorder traversal of the BST gives elements in SORTED order (non decreasing order).

So, input of QuickSort is SORTED ARRAY.

This is the WORST case scenario of Quick Sort.

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.

Hence Time Complexity :

= O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.