Suppose we want to sort n elements that have at most k different values where k<

Question

Suppose we want to sort n elements that have at most k different values where k<= n. (In other words, there are n - k duplicate values among elements.) The elements are of an arbitrary type for which there is a comparison operation.

a) Design an algorithm using pseudocode that sorts these elements in O(kn) time. Here the number of distinct values k, and the values themselves, are not known in advance.

(Note: when k is smaller than logn, this improves on the O(nlogn) time bound for general comparison-based sorting. In contrast to Counting Sort, the elements can be real numbers of even very large integers)

(Hint: Make use of a search tree. Choose an appropriate type for the item field of tree nodes, and recall an important property of in-order traversals of search trees.)

b) Implement the above search tree so that all their operations on a tree of n elements take O(logn) time and sorts the tree in O(nlogk) time.

Explanation / Answer

algorithm for part a

) first create a node with following fields :-

struct node

{

int data;

node*left;

node*right;

int count;

}

2)now we will construct an BST such that:-

if a node is not present int he tree then insert it;

else

if the node is present in the tree then just increase the count by 1;

3)

now we have to just do inorder traversal of the tree which will be slightly different than ordinary inorder traversal.

instead of printing the node just once we have to print the node count times.

Complexity

we know that insertion in an BST tree takes O(H) time where H is the Heiht of the tree..............since there are only

K nodes in the tree(rest are duplicates and are represented by variable count in node) therefore

H = O(logK) and

H = K in worst case situation;

therefore insertion of 1 node will take O(logK) time or O(k) time in worst case..............

since we have n nodes therefore total time to build the tree is O(N*logK) in best case scenario and O(k*n) in worst case scanrio

hence the complexity of the algorithm is O(N*K) in worst case scenario

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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