fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.     private static int partition3(int[] a){
  11.         // invariant: [ even | i ... j | uneven ]
  12.  
  13.         int front = 0;
  14.         int back = a.length - 1;
  15.         int comps = 0;
  16.  
  17.         // no tmp array!!
  18.         int tmp;
  19.         while (front < back){
  20.             comps += 2; // every time we test a[front], and sometimes a[back] too.
  21.             if (a[front] % 2 == 0){
  22.                 front++;
  23.                 comps--; // we're not testing a[back].
  24.             } else if (a[back] % 2 == 1){
  25.                 back--;
  26.             } else { // number at front is uneven and number at back is even
  27.                 tmp = a[front];
  28.                 a[front] = a[back];
  29.                 a[back] = tmp;
  30.                 front++;
  31.                 back--;
  32.             }
  33.         }
  34.         return comps;
  35.     }
  36.  
  37.     private static int partitionR(int[] a){
  38.         int front = 0;
  39.         int back = a.length - 1;
  40.         int comps = 0;
  41.  
  42.         // no tmp array!!
  43.         while (front < back){
  44.             comps++;
  45.             while (front < back && (a[front] & 1) == 0) {
  46.                 front++;
  47.                 if (front < back) {
  48.                     comps++;
  49.                 }
  50.             }
  51.             if (front < back) {
  52.                 comps++;
  53.             }
  54.             while (front < back && (a[back] & 1) == 1) {
  55.                 back--;
  56.                 if (front < back) {
  57.                     comps++;
  58.                 }
  59.             }
  60.             // swap the back evennumber with the odd front number
  61.             // occasionally front may == back.
  62.             int tmp = a[front];
  63.             a[front] = a[back];
  64.             a[back] = tmp;
  65.             front++;
  66.             back--;
  67.         }
  68.         return comps;
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.         int[][] tests = {
  73.                 {1,3,5,7,9,11,13,15,17,19},
  74.                 {1,2,3,4,5,6,7,8,9,10},
  75.                 {2,4,6,8,10,12,14,16}
  76.         };
  77.  
  78.         for (int[] data : tests) {
  79.             int[] copy3 = Arrays.copyOf(data, data.length);
  80.             int[] copyR = Arrays.copyOf(data, data.length);
  81.             int c3 = partition3(copy3);
  82.             int cR = partitionR(copyR);
  83.             System.out.printf("Input data %s\n 3 gives %d comps with output %s\n R gives %d comps with output %s\n",
  84.                     Arrays.toString(data), c3, Arrays.toString(copy3), cR, Arrays.toString(copyR));
  85.  
  86.  
  87.         }
  88.     }
  89. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input data [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 3 gives 18 comps with output [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 R gives 10 comps with output [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Input data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 3 gives 12 comps with output [10, 2, 8, 4, 6, 5, 7, 3, 9, 1]
 R gives 10 comps with output [10, 2, 8, 4, 6, 5, 7, 3, 9, 1]
Input data [2, 4, 6, 8, 10, 12, 14, 16]
 3 gives 7 comps with output [2, 4, 6, 8, 10, 12, 14, 16]
 R gives 7 comps with output [2, 4, 6, 8, 10, 12, 14, 16]
https://ideone.com/8wOzmB
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!