title: Sorting arrays in Java using the flag-sort
body: <p>Write a static method in Java :</p>
  
  <pre><code>public static void sortByFour (int[] arr)
  </code></pre>
  
  <p>That receives as a paramater an array full of non-negative numbers (zero or positive) and sorts the array in the following way :</p>
  
  <ul>
  <li>In the beginning of the array all the numbers that devide by four without a remainder will appear.</li>
  <li>After them all the numbers in the array that devide by 4 with a remainder of 1 will appear.</li>
  <li>After them all the numbers in the array that devide by 4 with a remainder of 2 will appear.</li>
  <li>In the end of the array all the rest numbers (those who divide by 4 with the remainder 3) will appear.</li>
  </ul>
  
  <p>(The order of the numbers in each group doesn't matter)</p>
  
  <p>The method must be the most efficient as possible using the flag-sort. The space complexity must be <strong>O(1)</strong> and the time complexity must be <strong>O(N)</strong> or less.</p>
  
  <p><strong>NOTE:</strong> Do NOT use an extra array.</p>
  
  <p>I read about the flag-sort but I don't know how to write the code of it in Java. Can someone please help me?</p>
  
  <p>According to what I read, it is necessary to find the start index and end index in the array of each of the buckets. Is that correct? For this it's necessary to count how many numbers in the array divide by four with a remainder of 0, 1, 2, and 3.</p>
  
  <p>Hmm...</p>
  
  <pre><code>public static void sortByFour(int[] arr) {
      int count1 = 0, count2 = 0, count3 = 0, count4 = 0;
      int startB1, startB2, startB3, startB4;
      for (int i = 0; i &lt; arr.length; i++) {
          if (arr[i] % 4 == 0)
              count1++;
          if (arr[i] % 4 == 1)
              count2++;
          if (arr[i] % 4 == 2)
              count3++;
          if (arr[i] % 4 == 3)
              count4++;
      }
      startB1 = 0;
      startB2 = startB1 + count1;
      startB3 = startB2 + count2;
      startB4 = startB3 + count3;
  
      for (int i = startB1; i &lt; arr.length; i++) {
          if (arr[i] % 4 == 0) {
              swap(arr[i], arr[startB1]);
              startB1++;
          }
      }
  
      for (int i = startB2; i &lt; arr.length; i++) {
          if (arr[i] % 4 == 1) {
              swap(arr[i], arr[startB2]);
              startB2++;
          }
      }
  
      for (int i = startB3; i &lt; arr.length; i++) {
          if (arr[i] % 4 == 2) {
              swap(arr[i], arr[startB3]);
              startB3++;
          }
      }
  }
  
  public static void swap(int a, int b) {
      int temp = a;
      a = b;
      b = temp;
  }
  </code></pre>
  
  <p>I am not sure it's correct though...</p>