CODEWITHSUNDEEP
algorithmsortingradix-sort
riderchap
riderchap

Reputation: 687

An array of length N can contain values 1,2,3 ... N^2. Is it possible to sort in O(n) time?

Given an array of length N. It can contain values from ranging from 1 to N^2 (N squared) both inclusive, values are integral. Is it possible to sort this array in O(N) time? If possible how?

Edit: This is not a homework.

Upvotes: 8

Views: 4699

Answers (3)

Yakov Galka
Yakov Galka

Reputation: 72519

Write each integer in base N, that is each x can be represented as (x1, x2) with x = 1 + x1 + x2*N. Now you can sort it twice with counting sort, once on x1 and once on x2, resulting in the sorted array.

EDIT: As others mentioned below, sorting on each 'digit' separately like this is is called a radix sort. Sorting on each digit with counting sort takes O(N) time and O(N) space (in this particular case). Since we repeat it exactly twice, this gives a total running time of O(N).

Upvotes: 10

Omnifarious
Omnifarious

Reputation: 56068

It is possible to sort any array of integers with a well defined maximum value in O(n) time using a radix sort. This is likely the case for any list of integers you encounter. For example if you were sorting a list of arbitrary precision integers it wouldn't be true. But all the C integral types have well-defined fixed ranges.

Upvotes: 0

svick
svick

Reputation: 244928

Yes, you can, using radix sort with N buckets and two passes. Basically, you treat the numbers as having 2 digits in base N.

Upvotes: 8

Related Questions