Geek Answers Handbook

Sort an array with elements from 0 to 9999

I recently ran into a C ++ issue. Here it goes.

Suppose you know that all values ​​in an integer array fall in the range from 0 to 9999. Show that you can write an O (N) algorithm to sort arrays with this restriction

As far as I understand, the O (N) algorithm is the one where you go through a certain set of operations O (1) N times. Now for life, I can’t understand how you are going to write a program that sorts an array of numbers relative to O (N). Sorting in the most basic form consists of comparing numbers with each other and there is no algorithm for this in one iteration and ends with a sorted array.

This question indicates that an element of this array can only have a value in the range 0-9999. I can understand from the question that this restriction is what does everything possible, and I must use it in my algorithm in order to reach a solution. But I still won’t go anywhere. All the sorting algorithms that I know (select, insert, merge, fast ...) have a runtime longer than O (N), with O (log N) being the minimum.

I understand that some of these algorithms may have O (N) runtimes, but only in their best cases. But I do not think that the question is being asked in this regard.

If anyone can shed light on this issue, I would appreciate it.

+5
source share
5 answers

Radix sort . O (4n) - O (n).

+5

(. http://en.wikipedia.org/wiki/Counting_sort). - Omega (n lg n).

+5
  • counts 10000 0.
  • a increment counts[a[i]] .
  • counts counts[i] i .
+2

: 10 000 . 10000 , , , , .

0
  • 10000
  • Set the value of the bit index for the number you are reading.
  • Read the bitrari again. If the bit is set, then this index, if your number is in sorted order.
0
source

More articles:


All Articles