well the requirement is only to sort the array Array repr: 9,6,21,1,7,16,36 (index starting from 1)
Now on sorting the array in place gives: 1,6,7,9,16,21,36 is a perfectly valid answer to the problem. No one is going to look at the result as a BST, it is going to be viewed as a sorted array. Its just a puzzle and not meant to be a practical problem. You can look at it this way, lets say there were two teams programming. One team was supposed to provide an ordered data structure which the other team was supposed to use. Due to some miscommunication the first team have produced a BST in an array as their ordered datastructure and the second team have wrote the code to take in a sorted array. We need to write a module that converts the BST to an array with no extra space and in O(n) time. Radix sort is a great algorithm alright but can you use inside the array itself? The major constraint is that you cannot use variable amount of extra space other than the given array. I dont think radix sort or counting sort will be able to do this without creating a new representation of the array (say as a list ..which involves O(n) extra space to store the pointers). I dont think there exists a O(n) bound with using the binary representation to sort the numbers. Atleast If you use the definition you have put forth directly. Radix sort is now an O(nk) sort where k=number of digits. In the binary representation k = lgn Leading to a O(nlgn) bound. Why is there an attempt to solve a bigger problem of sorting here? The given array has a nice order in that it a BST, we are converting it to a different order. Sorting is a much harder problem since the given elements need not be in order. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
