CODEWITHSUNDEEP
algorithmsortingbig-o
Habit
Habit

Reputation: 845

Which sorting algorithm should be used that runs in O(n)?

I'm having a difficult time trying to figure out which algorithms are the best to use for certain specifications.

Here's the prompt:

Write an algorithm to sort n integers, each in the range [0..((n^4)-1)] in O(n) time.

I'm more of a visual learner and understand best with examples. I made up values for this to visualize it, but I don't know what sorting method to use or how to figure out which to use. Any tips or suggestions are greatly appreciated. Thanks!

Upvotes: 2

Views: 160

Answers (3)

GregRos
GregRos

Reputation: 9113

Like I said in my comment, the only way to do this, as far as I know, is radix sort. You basically sort the numbers by comparing each digit separately.

The full complexity of the algorithm is O(d(n + b)), where b is the basis chosen and d is the number of digits in that basis. You can choose any basis pretty much, and work with the numbers in that basis.

The trick here is to choose the right basis. There exists a basis that would make the algorithm O(n), but if you just use base 2, each number would have up to O(4 logn) digits and so the total complexity would be O(n logn).

As a hint, there exists a basis in which each number in the range would have a constant number of digits.

Upvotes: 9

Robert Weller
Robert Weller

Reputation: 109

Radix sort is the only sorting algorithm I know of that can run in linear time.

Here is a link that should be helpful - Radix Sort implemented in C++

Upvotes: 3

Zachary K
Zachary K

Reputation: 3335

As far as I know there are no sort algorithms that run in O(n), Bubble sort runs in O(n^2). Quick sort runs in O(n log n)

Upvotes: -5

Related Questions