homework questions 1) What is the main reason to use the 3-way Quicksort? In oth

Question

homework questions

1)

What is the main reason to use the  3-way Quicksort?
In other words: in which situation is the 3-way Quicksort significantly faster than the 'traditional' quicksort?

2)

The Euclidean algorithm is an effective way to calculate the greatest common divisor (gcd)             
Complete the sentence below based on the method gcd

The base case is in line:

a) 03

b) 05

c) 03 and 05

d) 00

the recursive case is in line:

a) 03

b) 05

c) 03 and 05

d) 00

3)

Assume you enter the following data in the order presented to create a Binary Search Tree:  
P N O Q M    

      Which of the trees is created?

1)What is the main reason to use the 3-way Quicksort? In other words: in which situation is the 3-way Quicksort significantly faster than the 'traditional' quicksort? 2)The Euclidean algorithm is an effective way to calculate the greatest common divisor (gcd) Complete the sentence below based on the method gcd The base case is in line: a) 03 b) 05 c) 03 and 05 d) 00 the recursive case is in line: a) 03 b) 05 c) 03 and 05 d) 00 3)Assume you enter the following data in the order presented to create a Binary Search Tree: Which of the trees is created?

Explanation / Answer

1) A three partition quicksort is used to achieve a complexity of O(log3(n)). However it becomes really useful when the data has a lot of duplicates. In normal cases it behaves like regular quuicksort with single pivot and the overhead of maintaining three partitions can be worse. You can find a comparison here
http://stackoverflow.com/questions/17080128/why-is-quicksort-single-pivot-faster-than-3-way-partition
Read the question description. The implementations are also given in the description

2) The base case is the statement which sets an end to a recursive call stack. Here the base case condition is in the checking of if(b==0) , which would stop the recursion . Hence, the base case is in the line numbered 03 "return a;"

The recursive statement is much easier to detect as it is just the statement which calls the function itself, which is line numbered 05 here.

3) SInce it is a BST, and not a balanced BSt. The first element will be at the root. Sp root will have P. SO options b) and c) are ruled out. Next N would go left subtree of P as N is smaller than P . Next element O would go to the left of P but right of N.Thus option a) is ruled out. SO the correct answer is d)

Hope this helps. If you have any doubts/queries, feel free to contact :)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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