Interview Question
Country: United States
The original question is what i have written.It has to be solved by selection sort and using language C.
@eugene.yarovoi, using R-B Tree we can store count of each string directly. This will give O(n*log(n)*log(n)) implementation. If we use hashing for counting, it will give O(n*log(n)) solution. { obviously i am ignoring string lengths in time complexity + overhead of collision avoidance }. So, it won't be better than radix sort but will outperform selection sort.
Better use counting or radix sort for string sorting.
- Cerberuz September 09, 2012If you want to use selection sort than simply replace the comparison with you custom comparator function which compares to strings based on ascii values of characters starting from 0th place.