It seems easy, sum all the elements in the array and then reset the array with those many '1's in the end and rest '0's in the beginning. Time complexity is also O(n) with constant space. So it seems the best and easy one.

But if you are OK with this, please read the question again - MINIMUM TIME, it doesn't mean the minimum complexity. In the above solutions you are having 2 passes, one for taking sum and another for setting the array.

This can be done in a single pass:

just start two pointers, ptr1 from starting of the array(I should say from -1) and ptr2 from end of the array(I should say from length of the array).

while ptr2>ptr1

increment ptr1

if (array[ptr1] == 0) continue;

else

decrement ptr2 until array[ptr2] == 1;

if(ptr2> ptr1)

swap array[ptr1] with array[ptr2]

C code:

#include <stdio.h>#define MAXSIZE 100#define SWAP(a,b) a^=b^=a^=bvoid main(){int array[MAXSIZE], i, j, len=-1;printf("Enter array of 0 and 1, enter -1 to discontinue: ");do{len++;scanf("%d",&array[len]);}while(array[len] != -1);i= 0;j = len;while(j>i){if(array[i] == 0){i++;continue;}while(array[--j] == 1);if(j>i)SWAP(array[i],array[j]);} }

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
AkashI am not able to provide proper indentation to the code in blogger.

I am also not able to write a proper for loop syntax here.

Any help on these will be appreciated.

AkashFor clubbing different numbers together in case of 0,1,2..

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Ashish KailaI sorted 0, 1, and 2 in one pass using dutch national flag algorithm. Here is the code:

///

/// Sort an array of 0, 1 and 2 in place (dutch national flag problem)

///

///

[TestMethod]

public void Sort0_1_And_2_InPlace()

{

int[] numbers = new [] {1, 0, 2, 2, 1, 0, 0, 1, 2, 1};

int start = 0;

int end = numbers.Length - 1;

int mid = 0;

while ((mid >= start) && (mid <= end))

{

switch (numbers[mid])

{

case 1:

mid++;

break;

case 2:

numbers[mid] = numbers[end];

numbers[end] = 2;

end--;

break;

case 0:

numbers[mid] = numbers[start];

numbers[start] = 0;

start++;

mid++;

break;

}

}

}

Akash@Ashish: Thanks for contributing.

Omar Mohammad OthmanIn the pseudocode before the C code,

decrement ptr2 until array[ptr2] == 1;should be

decrement ptr2 until array[ptr2] == 0;.nitin guptaProgram for sorting array containing 0,1 and 2.

void sort(int [] arr)

{

int i0 = i1 = i2 = 0;

int high = sizeof(arr)/sizeof(int)-1;

for(;i2 <= high;)

{

arr[i2] == 0 ? swap(i0++; i2++) : arr[i2] == 1 ? i2++; i1++; : swap(arr[i2],arr[high--]);

}

}

void swap(int a, int b)

{

int temp = a;

a = b;

b = temp;

}

}