I red already that the best sort comparison algorithms have complexity O(nlog(n)). But I'm asked to sort an array of integers(in C) using a sorting algorithm of complexity O(n) given that all the elements in the array are non-negative and less than a constant K. But I have no idea how to use this information in the sorting algorithm. You guys have any idea?
4 Answers
That's a simple one (known as "counting sort" or "histogram sort", a degenerate case of "bucket sort"):
- Allocate an array with one slot for each non-negative integer less than
k, and zero it.O(k) - Iterate over all elements of the input and count them in our array.
O(n) - Iterate over our array and write the elements out in-order.
O(n+k)
Thus, O(n+k).
2 Comments
rcgldr
If step 2. is O(n), reading n elements and incrementing (read + write) the array of k elements n times, then wouldn't step 3 also be O(n), reading and decrementing the array of k elements n times and writing n elements?
Deduplicator
@rcgldr: In step 2, we iterate over the input array (length n) once, and do the same simple operation for each. Thus, O(n). In step 3, we iterate over our side-array (length k), writing into our output-array exactly n times in the process, so O(iter+write) == O(k+n).
Radix sort gives you O(n log k), not O(n log n) complexity. Since K is a fixed number independent of n, the resultant complexity is O(n * const), I.e. It is linear.
answered Dec 7, 2014 at 20:45
Sergey Kalinichenko
729k85 gold badges1.2k silver badges1.6k bronze badges
Comments
create a new array of size K and just insert each element to the array in it own position..
lets say K=100
create an array of 100 integers - clear it. and if you have the set {55, 2, 7, 34}. you just need to the following:
array[55] = 1;
array[2] = 1;
array[7] = 1;
array[34] =1;
And the go over the array from start to end and just print the index of the cells that are == 1
Comments
Depends on the kind of complexity. Average case O(n+k): Bucket Sort.
Radix sort should be O(m * n) though. (m being the length of the key used to sort)
1 Comment
Sneftel
If K is the maximum number (as opposed to the number of bits) then radix sort is
O(n log K), not O(nK).
O(n log n).