Algorithms-and-Data-Structures-in-Java/src/main/java/com/rampatra/arrays/Segregate0sAnd1s.java at master · bm01wait/Algorithms-and-Data-Structures-in-Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package com.rampatra.arrays;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 *
 * @author rampatra
 * @since 7/31/15
 * @time: 5:13 PM
 */
public class Segregate0sAnd1s {

    /**
     * Segregate 0s and 1s by traversing the array only once.
     *
     * @param a
     */
    public static void segregate0sAnd1s(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            if (a[i] > a[j]) {
                // swap if a[i] > a[j]
                a[i] = a[i] + a[j];
                a[j] = a[i] - a[j];
                a[i] = a[i] - a[j];
            }
        }
    }

    public static void main(String[] args) {
        int[] ar = new int[]{0, 1, 1, 1, 0, 0, 1};
        segregate0sAnd1s(ar);
        System.out.println(Arrays.toString(ar));
    }
}