CareerCup

Dutch national flag problem

Use counting sort.

package com.program;

public class Sort0s1s2s {

public static void main(String[] args) {

int arr[] = { 0, 1, 1, 0, 1, 2, 1,
2, 0, 0, 0, 1 };
int n = 12;
sort012(arr, n);
for(int i=0;i<n;i++) {
System.out.print(arr[i]+" -");
}
}

private static void sort012(int[] arr, int n) {

int count0s=0;
int count1s=0;
int count2s=0;

for(int i=0;i<n;i++) {
if(arr[i]==0) {
count0s++;
}
if(arr[i]==1) {
count1s++;
}
if(arr[i]==2) {
count2s++;
}
}
for(int i=0;i<count0s;i++) {
arr[i]=0;
}
for(int i=count0s;i<count0s+count1s;i++) {
arr[i]=1;
}
for(int i=count0s+count1s;i<count0s+count1s+count2s;i++) {
arr[i]=2;
}

}

}

I think it is a bit simpler than the "Dutch national flag problem".
It resolves to range count instead of high/mid/low sort.

void CountSort(int beg, int end, std::vector<int> v)
{
	std::vector<int> counts(end - beg + 1, 0);
	for (int i : v)
		counts[i - beg]++;
	auto start = v.begin();
	for (int i = beg; i <= end; i++)
              start = std::fill_n(start, counts[i - beg], i);
}

public class ArrangeZeroOneTwo {
public static void main(String arv[]) {
int arr[] = {1,0,1,2,0,2,0,2,1,0,2,1,0,1,1,1,1,1,2,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,0,0,0,0,0,0};
int pointerForZero=0;
int pointerForTwo=arr.length-1;
for(int i=0;i<arr.length && i<pointerForTwo ;i++) {
if(arr[i] == 0) {
arr[i] = arr[pointerForZero];
arr[pointerForZero] = 0;
++pointerForZero;
}
if(arr[i] == 2) {
arr[i] = arr[pointerForTwo];
arr[pointerForTwo] = 2;
--pointerForTwo;
--i;
}
}
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i] +" ");
}
}
}

A solution in q language:

f:{ / function to sort the elements of the array
    c0::c1::c2::0; / counter variables
    {$[0=x;c0+:1;1=x;c1+:1;2=x;c2+:1;::]} each x; / inner function to count occurrence of each element
    :raze [[(c0;c1;c2)]{#[x;y]}'til 3]; / returning the occurrence of 0,1,2 based on count
    };

Test:
a:0 1 1 0 2 1 2; / array initialization
f a / calling the function
Output: 0 0 1 1 1 2 2

k solution:

f:{c0::c1::c2::0;{$[0=x;c0+:1;1=x;c1+:1;2=x;c2+:1;::]}'x;,/(c0;c1;c2){#[x;y]}'!3}

Test:
> f 0 1 1 0 2 1 2 /- output 0 0 1 1 1 2 2
> f 0 1 2 0 1 2 0 1 2 /- output - 0 0 0 1 1 1 2 2 2

int[] ar = {1,1,0,0,1,1,0,0,1,1,2,2,2,2,1,1,1,1,0,0,0};
        int[] c = new int[3];
        
        for(int i=0; i<ar.length; i++){
            if(ar[i] == 0) c[0]++;
            else if(ar[i] == 1) c[1]++;
            else c[2]++;
        }
        
        for(int i=0; i<c.length; i++){
             while(c[i]-- > 0){
                 System.out.print(i + " ");
             }
        }

int[] ar = {1,1,0,0,1,1,0,0,1,1,2,2,2,2,1,1,1,1,0,0,0};
        int[] c = new int[3];
        
        for(int i=0; i<ar.length; i++){
            if(ar[i] == 0) c[0]++;
            else if(ar[i] == 1) c[1]++;
            else c[2]++;
        }
        
        for(int i=0; i<c.length; i++){
             while(c[i]-- > 0){
                 System.out.print(i + " ");
             }
        }

Logic: COunt the number of 1, 2 and 3 in the array, and then iterate again to write them in order as per the counts. will take two traversal though.

Lets make it little complex , what if only one iteration is allowed

from collections import Counter
input_list = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
val = Counter(input_list)
for i in val.keys():
j=1
while j <= val[i]:
print(i)
j += 1