Piskomerka

gistfile1.java

package com.stackoverflow;

import java.util.Random;

public class ZeroOneSorting {
    static Random random = new Random();

    public static void main(String[] args) {

        int LENGTH = 1_00_000_000; long before, after;
        System.out.println("Generating arrays...");
        byte[] arr = generate(LENGTH);
        byte[] copy = new byte[LENGTH];
        System.arraycopy(arr, 0, copy, 0, LENGTH);
        System.out.println("Sorting...");
        System.out.println("Misha>");
        before = System.currentTimeMillis();
        sortMisha(copy);
        after = System.currentTimeMillis() - before;
        System.out.println("Time passed: " + after);
        System.out.println("Andrey>");
        before = System.currentTimeMillis();
        sortAndrey(arr);
        after = System.currentTimeMillis() - before;
        System.out.println("Time passed: " + after);
        System.out.println("Andrey2>");
        before = System.currentTimeMillis();
        sortAndrey2(arr);
        after = System.currentTimeMillis() - before;
        System.out.println("Time passed: " + after);
    }

    static byte[] generate(int n) {
        byte[] arr = new byte[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (byte) random.nextInt(2);
        }
        return arr;
    }

    public static void sortAndrey(byte[] s) 
    { 
         int i0 = 0, i1 = s.length - 1; 
          
         while (i0<i1) { 
              if (s[i0] == 0){ 
                   i0++; 
                   continue; 
              }                     
              else { 
                   if (s[i1] == 0) { 
                        s[i0] = 0; s[i1] = 1; 
                   } 
                   else i1--; 
              } 
         } 
    }
    
    public static void sortAndrey2(byte[] s)  
    {  
         int i0 = 0, i1 = s.length - 1;  
           
         while (i0<i1) {  
              if (s[i0] == 0){  
                   i0++;  
              } else if (s[i1] == 0) {  
                        s[i0] = 0; 
                        s[i1] = 1;  
                        i0++; 
                        i1--; 
              } else i1--;  
         }  
    }

    public static void sortMisha(byte[] s) {
        int zeros = 0;
        for (int i = 0; i < s.length; i++) {
            zeros += s[i];
        }

        for (int i = 0; i < zeros; i++) {
            s[i] = 0;
        }
        
        for (int i = zeros; i < s.length; i++) {
            s[i] = 1;
        }
    }
}