3

Here's a brain teaser that's been on my mind for a few days.

We have a sequence S of n elements. Each element is an integer in the range [0, n^2-1]. Describe a simple method for sorting S in O(n) time.

Probably something obvious that I am just missing, but I'd appreciate any insight.

Improve this question

4 Answers 4

Reset to default
4

Bucket Sort!

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Not really O(n) (something like O(n + X) where X is taken to go through the n² cells...) and regarding space with n² ...
@ring0 : Create n^2 buckets. Sorts S in O(n) time and O(n^2) space so meets asker's criterion.
If you're following the bucket sort description on the wikipedia page, then the final step of bucket sort is to visit the buckets in order to gather the elements. If you're sorting into n^2 buckets, then it will take O(n^2) time to do the gathering step.
@Soldier You get a sorted S². Complexity should take into account the time taken to go from S² to S (likely to be O(n²)). Complexity O(n) is achieved when N elements e are each between 0 <= e < N. Moreover the author doesn't mention that all elements are unique. Thus the algorithm will miss duplicates - unless you implement counters ( like T[ e ]++ ), this should be part of the solution.
O(n) space can be achieved, see my answer.
2

Radix Sort! (which is just a special case of bucket sort.)

Improve this answer

Comments

2

Write in base n and do a bucket sort, by doing a counting sort for each bucket (buckets correspond to digits in base n).

O(n) time, O(n) space.

Improve this answer

1 Comment

It seems like it would actually be O(n (1 + (log k)/(log n))) according to this page: ics.uci.edu/~eppstein/161/960123.html
0

Quicksort is O(n log n), as the standard "good algo" way to sort a list. So there has to be some kind of "trick" to get down to O(n) time.

The only real trick to this data is it goes from 0 to n^2-1... but I can't think of how this could be used to sort in O(n) time....

P.S. Sounds like homework, not something you would "puzzle on for the sake of knowledge"

P.P.S. I fail for not thinking of bucket sort.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.