2008/12/13 Ben Schmidt: > > Aram Havarneanu wrote: >> David Hláčik wrote: >>> I have to create stable algorithm for sorting n numbers from interval >>> [1,n^2] with time complexity O(n) . >> >> Count sort? >> >> http://en.wikipedia.org/wiki/Counting_sort >> >> It's time complexity is O(n), but space complexity in your case is O(n^2). > > I would say it's not O(n). It has to iterate the count array, so it's > O(n^2) in this case. Though it depends a little how you measure. > However, since we are just sorting numbers, I'd say an access to the > count array should be counted equally to an access to the array being > sorted. > > Not that I have an alternative proposal at this stage...
I've never seen an algorithm for sorting that's better than O(n log n) on average. Are there any? I can't even imagine how a sort could possibly be done in O(n) time, since that would require looking at each element only once... That being said, if I had to quickly write a program that had a speedy stable sort, I'd either write it in C++ and use std::stable_sort() (if I weren't a student doing this for a class) or try my hand at writing a merge sort that makes decent use of locality of reference to be fast enough (if I knew a professor would fail me for using std::stable_sort()). ~Matt --~--~---------~--~----~------------~-------~--~----~ You received this message from the "vim_use" maillist. For more information, visit http://www.vim.org/maillist.php -~----------~----~----~----~------~----~------~--~---
