1. Draw the BST that results when the words are inserted in the order given belo
ID: 3874396 • Letter: 1
Question
1. Draw the BST that results when the words are inserted in the order given below.
using, while, static, private, enum, case, return, public < 8 >
2. Given the preorder and inorder traversals of a binary tree, you build that binary tree.
< 8 >
Preorder: X B G Y D E C N
Inorder: Y G B D X E C N
3. (a) Under what type of data arrangement; Quick sort works at its worst efficiency?
< 2>
___________________________________________
(c) When do you use external sorts?
< 2 >
4. Show the various splitting and merging stages of Binary merge sort for the following list of numbers. < 8 >
8 21 13 35 16 10 48 32
Explanation / Answer
3)a)Answer:
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.
(c) When do you use external sorts?
Answer:
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted sub-files are combined into a single larger file.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.