I have a boolean array. How can I sort it so that at first there are only false values, and after them only true values?

    7 answers 7

      Boolean[] array = {true, false, true, false, true, true}; List<Boolean> sorted = Arrays.stream(array).sorted().collect(Collectors.toList()); sorted.stream().forEach(f -> System.out.println(f));

    result

     false false true true true true

    https://ideone.com/KYePDt

    The advantage of this method is that stream() can be easily replaced with parallelStream() for big data.

    • Isn't it easier to call Arrays.parallelSort() , which it Arrays.parallelSort() rests on under the hood? - etki

    This problem definitely needs to be solved by sorting by calculation , since we have only two possible values. As a result, the complexity of the algorithm is O(n) ; in your particular case, you can write it like this

     public static boolean[] sortBooleans(boolean[] array) { int fc = 0; for(boolean b:array) if(!b) fc++; boolean[] narray = new boolean[array.length]; for(int i = 0; i < fc; i++) narray[i] = false; for(int i = fc; i < narray.length; i++) narray[i] = true; return narray; }

    A summary of the case of m possible values ​​can be viewed by reference .

    • string for (int i = 0; i <fc; i ++) narray [i] = false; can be removed - Russtam

    And how many elements are in the array? If enough is enough, then it can be easier to do this.

     public boolean[] sortBooleanArray(boolean[] in) { int trueCount = 0; for (boolean b : in) { if (b) trueCount++; } boolean[] out = new boolean[in.length]; boolean[] trueOut = new boolean[trueCount]; Arrays.fill(trueOut, true); System.arraycopy(trueOut, 0, out, in.length - trueCount, trueCount); return out; }
    • But isn't it too much to create an additional array and copy from an array to an array? In my opinion, it's easier to simply set the true value in the right elements of the out array. Something like this: an example . - Regent
    • Busting is when the loop is actually :) If you are interested, you can do load testing of both options. - rjhdby
    • Something tells me that Arrays.fill and System.arraycopy can be faster - you have to go into the implementation. - rjhdby

    You can use any sorting algorithm, the only difference is how to compare them, because the <> operator is not suitable for comparing variables of type boolean :

     boolean[] arr = {true, false, true, true, false}; for (int i = 0 ; i < arr.length; i++) { for (int j = i+1; j < arr.length; j++) { if (arr[i] && !arr[j]) { arr[i] = false; arr[j] = true; } } } for (int i = 0; i < arr.length; i++) System.out.println(arr[i]);

    Conclusion :

    enter image description here

    • Within the framework of optimization, it makes sense to bring if (arr[i]) beyond the internal loop, and add break to the internal if . An example . - Regent
    • one
      Within the framework of optimization, @Regent should write a normal algorithm for O (n), and not the one that works for O (n ^ 2) - Igor Fedorov

    A more classic version, using one cycle.

     int current = 0; for (int i = 0; i < array.length; i++) { if (array[i]) continue; array[i] = true; array[current] = false; current++; }
    • current can also be added to for - Grundy
    • how? we need to memorize the leftmost position for insertion when iterating over an array. - Artem Konovalov
    • I meant the definition: int i = 0,current = 0; - Grundy
    • This is definitely a taste, but I don’t like to write so much - it’s bad to read - Artem Konovalov
    • but then the variable that is used only in the loop does not hang out - Grundy

    Do not use in production'e)

     boolean[] array = {true, false, true, false, true, true}; Stream .generate( new Supplier<Boolean>() { private int index = 0; @Override public Boolean get() { return array[index++]; } }) .limit(array.length) .sorted() .forEach(System.out::println);

      Option without creating a new array.

       public static void main(String[] args) { boolean[] arr = new boolean[10]; Random r = new Random(); int counter = 0; for (int x = 0; x < arr.length; x++) { arr[x] = r.nextBoolean(); // заполнение массива случайными значениями boolean } for (boolean x : arr) { if (!x) counter++; // подсчет количества значений false в изначальном массиве } Arrays.fill(arr, 0, counter, false); // заполнение первых значений массива согласно подсчета количества false значений Arrays.fill(arr, counter, arr.length, true); // остальные элементы массива заполнятся значениями true }