A sorting algorithm that does not allow counting elements

Question

I saw how companies interviewed this question in an interview, but at first I did not quite understand the question. Could you people clarify my doubts?

Question: Write a program for sorting an integer array that contains only 0, 1 and 2. Counting elements is not allowed, you must do this in O (n) time complexity.

Ex Array: {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}

Answer 1

Since there are so few values ​​in the array, just count the number of each of them and use this to refill the array. We also use the fact that the values ​​are sequentially from 0 to - this corresponds to a typical java int loop.

The entire sorting algorithm requires only three lines of code:

public static void main(String[] args) { int[] array = { 2, 0, 1, 2, 1, 2, 1, 0, 2, 0 }; // Line 1: Define some space to hold the totals int[] counts = new int[3]; // To store the (3) different totals // Line 2: Get the total of each type for (int i : array) counts[i]++; // Line 3: Write the appropriate number of each type consecutively back into the array: for (int i = 0, start = 0; i < counts.length; start += counts[i++]) Arrays.fill(array, start, start + counts[i], i); System.out.println(Arrays.toString(array)); } 

Conclusion:

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

Without ever referring to array.length , don't worry about how long the array has been. It is repeated through an array touching each element only once, making this algorithm O (n) as necessary.

Answer 2

List in a linked list.

• Remember the beginning of the list.
• Remember the position at which 1s begins.
• Remember the end of the list.

Run the entire array.

• If you encounter 0, add it to the first position of the linked list.
• If you encounter 1, add it after position 1.
• If you meet 2, add them to the end of the list.

NTN

Cancer

Answer 3

Instead of setting you on fire with yet another obscure pseudo-code, I will give you the name of the problem: this problem is known as the Dutch national flag problem (first proposed by Edsgar Dijkstra) and can be resolved by trilateral merging (see the PHP code in the first answer that resolves this , although very inefficient).

A more efficient threeways merger solution is described in the original paper by Bentleys and McIlroys Engineering Sort Function . It uses four indexes to delimit the ranges of an intermediate array that has unsorted values ​​in the middle, 1 on both edges and 0 and 2 seconds between them:

After establishing this invariant, the parts = (i.e. 1s) are replaced back to the middle.

Answer 4

It depends on what you mean by "without regard to what is permissible."

One easy way to do this is to create a new empty array and then search for 0 by adding them to the new array. Repeat for 1, then 2, and it is sorted in O (n) time.

But it is more or less radial sorting. This is like we are counting 0, then 1, then 2, so I'm not sure if this fits your criteria.

---

Edit: we could only do this with O (1) extra memory by pointing to our insertion point (starting at the beginning of the array) and looking at the array for 0, replacing each 0 with the element where the pointer is and increasing the pointer. Then repeat for 1, 2 and another O (n).

Java implementation:

 import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] array = {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}; sort(array); System.out.println(Arrays.toString(array)); } public static void sort(int[] array) { int pointer = 0; for(int i = 0; i < 3; i++) { for(int j = 0; j < array.length; j++) { if(array[j] == i) { int temp = array[pointer]; array[pointer] = array[j]; array[j] = temp; pointer++; } } } } } 

Gives output:

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

Answer 5

Sorry, this is php, but it seems O (n) and can be easily written in java :)

 $arr = array(2, 0, 1, 2, 1, 2, 1, 0, 2, 0); $tmp = array(array(),array(),array()); foreach($arr as $i){ $tmp[$i][] = $i; } print_r(array_merge($tmp[0],$tmp[1],$tmp[2])); 

Answer 6

In O (n) pseudo code:

 def sort (src): # Create an empty array, and set pointer to its start. def dest as array[sizeof src] pto = 0 # For every possible value. for val in 0, 1, 2: # Check every position in the source. for pfrom ranges from 0 to sizeof(src): # And transfer if matching (includes update of dest pointer). if src[pfrom] is val: dest[pto] = val pto = pto + 1 # Return the new array (or transfer it back to the source if desired). return dest 

This is basically iterating over the list of sources three times, adding elements if they match the required value on this pass. But he is still O (n).

The equivalent Java code would be:

 class Test { public static int [] mySort (int [] src) { int [] dest = new int[src.length]; int pto = 0; for (int val = 0; val < 3; val++) for (int pfrom = 0; pfrom < src.length; pfrom++) if (src[pfrom] == val) dest[pto++] = val; return dest; } public static void main(String args[]) { int [] arr1 = {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}; int [] arr2 = mySort (arr1); for (int i = 0; i < arr2.length; i++) System.out.println ("Array[" + i + "] = " + arr2[i]); } } 

which outputs:

 Array[0] = 0 Array[1] = 0 Array[2] = 0 Array[3] = 1 Array[4] = 1 Array[5] = 1 Array[6] = 2 Array[7] = 2 Array[8] = 2 Array[9] = 2 

---

But seriously, if a potential employer asked me this question, I would directly say that I can answer the question if they wish, but the correct answer is simply to use Array.sort . Then, if and only if there is a problem with this method and specific data sets, you can explore a faster way.

And this faster way would almost certainly include counting, despite the requirements. You do not complicate the work of your developers with arbitrary restrictions. Requirements should indicate what is required, not how.

If you answered this question to me in this way, I would hire you locally.

Answer 7

This answer does not account for elements.

Since there are so few values ​​in the array, just count the number of each of them and use this to refill the array. We also use the fact that the values ​​are sequentially from 0 to - this corresponds to a typical java int loop.

 public static void main(String[] args) throws Exception { Integer[] array = { 2, 0, 1, 2, 1, 2, 1, 0, 2, 0 }; List<Integer>[] elements = new ArrayList[3]; // To store the different element types // Initialize the array with new lists for (int i = 0; i < elements.length; i++) elements[i] = new ArrayList<Integer>(); // Populate the lists for (int i : array) elements[i].add(i); for (int i = 0, start = 0; i < elements.length; start += elements[i++].size()) System.arraycopy(elements[i].toArray(), 0, array, start, elements[i].size()); System.out.println(Arrays.toString(array)); } 

Conclusion:

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

Answer 8

Push and Pull have constant difficulty!

• Insert each item in the priority queue

• Pull each item at indices 0 ... n

(

Answer 9

You can do this in one go by placing each colliding element in the final position:

 void sort012(int* array, int len) { int* p0 = array; int* p2 = array + len; for (int* p = array; p <= p2; ) { if (*p == 0) { std::swap(*p, *p0); p0++; p++; } else if (*p == 2) { std::swap(*p, *p2); p2--; } else { p++; } } }