In the worst case, sorting n strings of length m each could take O(n m log n) time. If we are sorting something like strings, this can get particularly expensive, because calls to strcmp may take time linear in the length of the strings being compared. Since there are n! possible ways to reorder the input sequence, this means we need at least log(n!) = O(n log n) calls to compare to finish the sort. This has a rather nice advantage of making the algorithm very general, but has the disadvantage that the algorithm can extract only one bit of information from every call to compare. This means that the only information the algorithm uses about the items it is sorting is the return value of the compare routine. The standard quicksort routine is an example of a comparison-based sorting algorithm. What's wrong with comparison-based sorting
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |