current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 0 down vote favorite

As I am reading a Book about "Algorithm Analysis", I came across count_sort Algorithm. A question has been raised in my head. I read in many other papers, that "Quick Sort/ Merge Sort" are the best and the most efficient sorting algorithms. However, the complexity of this Algorithms is O(n+k), same for Quick sort, and better than Merge sort O(n ln n).

My question:

  • What is the problem with this sorting Algorithm.

  • What are the best sorting Algorithms that I have to check ?

    def count_sort(seq):
    b, c = [], defaultdict(list)
    for x in seq:
        c[x].append(x)

    for k in range(min(c), max(c)+1):
        b.extend(c[k])
    return b
share|improve this question
    
Why do you say that this is O(n+k)? How do you think defaultdict is implemented? –  Greg Hewgill Sep 2 '14 at 2:27
    
defaultdict is a python package check: stackoverflow.com/questions/5900578/… –  user3001937 Sep 2 '14 at 21:13
    
Yes, I know what defaultdict is. However, using it is not free in terms of complexity. –  Greg Hewgill Sep 2 '14 at 21:15
    
True ! I wanted to illustrate how can we build sort algo in a very quick way. But still that we can remplace it with L= [{x:x} for x in list seq] –  user3001937 Sep 2 '14 at 21:17

1 Answer 1

up vote 1 down vote

Counting sorts fail when there are large key values (the k in the O(n)). This means that if you have a large variety of key values, counting sort will be slow. Radix sort can help solve that problem but it does nothing for other issue. Both counting and radix sort are only valid for integer keys. While not a terribly serious limitation, it does mean that Radix Sort's value for the number of digits in a key should not be considered constant.

There's also the small matter of space complexity and stability of sorting. Radix sort requires a stable sorting algorithm to be used as a subsort. Counting sort is stable, provided that you use a separate input and output structure. If you don't then you wind up with an unstable sort. That is, you may wind up with elements in the wrong order.

"Best" is a very loaded term. There is no "best" sorting algorithm. It will depend on a variety of factors including time complexity, space complexity, ability to parallelize the implementation and the ease of implementation.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.