Advertisement
Guest User

Recursive Bubble Sort!

a guest
Sep 28th, 2012
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Bt {
  2.     int[] unsorted={3,5,2,0,1,8,6,-1};
  3.     int[] candidate;
  4.     int[] best;
  5.     public static void main (String[] args) {
  6.         Bt b= new Bt();
  7.         b.bt();
  8.         b.print(b.best);
  9.     }
  10.     void bt() {
  11.         if (accept (candidate)) {
  12.             best= new int[candidate.length];
  13.             System.arraycopy (candidate, 0, best, 0, candidate.length);
  14.             return;
  15.             //System.exit (0);
  16.         }
  17.         if (reject (candidate)) return;
  18.         if (!augment ()) return;
  19.         do {
  20.             bt();
  21.         } while (next());
  22.         diminish ();
  23.     }
  24.     public boolean augment () {
  25.         if (candidate==null) {
  26.             candidate= new int[1];
  27.             candidate[0]=0;
  28.             return true;
  29.         }
  30.         int i;
  31.         boolean b[]= new boolean [unsorted.length];
  32.         // add the smallest index not present
  33.         for (i=0;i<candidate.length;i++)
  34.             b[candidate[i]]=true;
  35. //      for (i=candidate[candidate.length-1];i<unsorted.length;i++)
  36.         for (i=0;i<unsorted.length;i++)
  37.             if (!b[i]) break;
  38.         // add one element if possible.
  39.         if(i<unsorted.length) {
  40.             int r[]= new int[candidate.length+1];
  41.             System.arraycopy (candidate, 0, r, 0, candidate.length);
  42.             r[r.length-1]=i;
  43.             candidate=r;
  44.             return true;
  45.         }
  46.         return false;
  47.     }
  48.     public boolean next () {
  49.         if (candidate==null) {
  50.             System.out.println ("cannot be empty.");
  51.             System.exit (0);
  52.         }
  53.         int i;
  54.         boolean b[]= new boolean [unsorted.length];
  55.         // add the smallest index not present
  56.         for (i=0;i<candidate.length;i++)
  57.             b[candidate[i]]=true;
  58.         for (i=candidate[candidate.length-1];i<unsorted.length;i++)
  59.             if (!b[i]) break;
  60.         // substitute the last element if possible.
  61.         if(i<unsorted.length) {
  62.             candidate[candidate.length-1]=i;
  63.             return true;
  64.         }
  65.         return false;
  66.     }
  67.     public void diminish () {
  68.         if ((candidate!=null)&&(candidate.length>0)) {
  69.             int r[]= new int[candidate.length-1];
  70.             System.arraycopy (candidate, 0, r, 0, candidate.length-1);
  71.             candidate=r;
  72.         }
  73.     }
  74.     public boolean accept (int[] candidate) {
  75.         if (candidate==null) return false;
  76.         if (!reject(candidate) && candidate.length==unsorted.length) return true;
  77.         return false;
  78.     }
  79.     public boolean reject (int[] candidate) {
  80.         if ((candidate==null)||(candidate.length<2)) return false;
  81.         int i;
  82.         for (i=1;i<candidate.length;i++)
  83.             if (unsorted[candidate[i-1]]>unsorted[candidate[i]]) return true;
  84.         return false;
  85.     }
  86.     public void print (int[] a) {
  87.         if (a==null) {
  88.             System.out.println ("Empty");
  89.             return;
  90.         }
  91.         for (int i=0;i<a.length;i++)
  92.             System.out.print (a[i] + " ");
  93.         System.out.println();
  94.     }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement