Posted by: khai_k_khai_k January 30, 2010
Login in to Rate this Post:
0 
? 
?
@Wai_Wai
What type of value does the List contains. If it's an integer then what will be the range??
As someone previously suggested, the sorting algorithm will depend on the type of value in the List.
There are couple of options:
1. Use a Heap (min heap). First insert all, then remove one by one. -- o(nlogn)
2. Use a lookup array. i.e. something like bucket sort. O(n + m) where n is the size of the list and m is the size of the lookup array
3. Insert all and remove all from a BST. -- O(nlogn)
For the requirement of O(n) I would rather go for bucket sort like algorithm:
First determine the range of values in the list.
And sort it based on the value or alternatively create a new List with those values.
What type of value does the List contains. If it's an integer then what will be the range??
As someone previously suggested, the sorting algorithm will depend on the type of value in the List.
There are couple of options:
1. Use a Heap (min heap). First insert all, then remove one by one. -- o(nlogn)
2. Use a lookup array. i.e. something like bucket sort. O(n + m) where n is the size of the list and m is the size of the lookup array
3. Insert all and remove all from a BST. -- O(nlogn)
For the requirement of O(n) I would rather go for bucket sort like algorithm:
First determine the range of values in the list.
And sort it based on the value or alternatively create a new List with those values.