java - Sorting algorithm which does not allow counting of elements -

java - Sorting algorithm which does not allow counting of elements -

i have seen acrosss in company interview test question, not clear question first. people clarify uncertainty ?

question : write programme sort integer array contains 0's,1's , 2's. counting of elements not allowed, expected in o(n) time complexity.

ex array : {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}

because there few values in array, count how many of each type there , utilize repopulate array. create utilize of fact values consecutive 0 - making match typical java int loop.

the whole sorting algorithm requires 3 lines of code:

public static void main(string[] args) { int[] array = { 2, 0, 1, 2, 1, 2, 1, 0, 2, 0 }; // line 1: define space hold totals int[] counts = new int[3]; // store (3) different totals // line 2: total of each type (int : array) counts[i]++; // line 3: write appropriate number of each type consecutively array: (int = 0, start = 0; < counts.length; start += counts[i++]) arrays.fill(array, start, start + counts[i], i); system.out.println(arrays.tostring(array)); }

output:

[0, 0, 0, 1, 1, 1, 2, 2, 2, 2]

at no time did refer array.length, no care how long array was. iterated through array touching each element once, making algorithm o(n) required.

java sorting