Merge pull request w0rthy#12 from Skeen/binaryQuickSort

w0rthy · web-flow · commit 69066004d7ca · 2019-02-25T15:15:09.000-06:00
Introduce binary QuickSort
diff --git a/src/array/visualizer/ArrayVisualizer.java b/src/array/visualizer/ArrayVisualizer.java
@@ -66,7 +66,7 @@ public class ArrayVisualizer {
     static ArrayList<Color> COLORSTRAT2cols = new ArrayList<Color>();
     
     static String[] ComparativeSorts = "Selection!Bubble!Insertion!Double Selection!Cocktail Shaker!Quick!Merge!Merge OOP!Weave Merge!Max Heap!Shell".split("!");
-    static String[] DistributiveSorts = "Radix LSD!Radix MSD!Radix LSD In-Place!Gravity!Shatter!Counting!Time!Bogo".split("!");
+    static String[] DistributiveSorts = "Radix LSD!Radix MSD!Radix LSD In-Place!Binary Quicksort!Gravity!Shatter!Counting!Time!Bogo".split("!");
     
     static int cx = 0;
     static int cy = 0;
@@ -657,6 +657,7 @@ public void run(){
                             new GravitySort(),
                             new RadixLSD(4),
                             new RadixMSD(4),
+                            new BinaryQuickSort(),
                             new RadixLSDInPlace(2),
                             new RadixLSDInPlace(10)}
                         )
@@ -766,14 +767,16 @@ public void run(){
                 case 2:
                     sort = new RadixLSDInPlace(base);break;
                 case 3:
-                    sort = new GravitySort();break;
+                    sort = new BinaryQuickSort();break;
                 case 4:
-                    sort = new ShatterSorts(base);break;
+                    sort = new GravitySort();break;
                 case 5:
-                    sort = new CountingSort();break;
+                    sort = new ShatterSorts(base);break;
                 case 6:
-                    sort = new TimeSort(base);break;
+                    sort = new CountingSort();break;
                 case 7:
+                    sort = new TimeSort(base);break;
+                case 8:
                     sort = new BogoSort();break;
                 default:
                     sort = null; break;
diff --git a/src/array/visualizer/sort/BinaryQuickSort.java b/src/array/visualizer/sort/BinaryQuickSort.java
@@ -0,0 +1,89 @@
+/*
+ * To change this template, choose Tools | Templates
+ * and open the template in the editor.
+ */
+package array.visualizer.sort;
+
+import array.visualizer.ArrayController;
+
+import static array.visualizer.ArrayVisualizer.*;
+import static array.visualizer.utils.Analysis.*;
+import static array.visualizer.utils.Swaps.*;
+
+/**
+ *
+ * @author Skeen
+ */
+public class BinaryQuickSort implements Sort {
+
+    public static boolean getBit(int n, int k) {
+        // Find boolean value of bit k in n
+        return ((n >> k) & 1) == 1;
+    }
+
+    public static int analyzeBit(final ArrayController ac) {
+        // Find highest bit of highest value
+        int max = 0;
+        for(int i = 0; i < ac.length; i++){
+            ac.marked.set(1, i);
+            ac.aa++;
+            sleep(1);
+            max = Math.max(max, ac.array[i]);
+        }
+        return 31 - Integer.numberOfLeadingZeros(max);
+    }
+
+    public static void binaryQuickSort(final ArrayController ac, int p, int r, int bit)
+    {
+        if (p < r && bit >= 0)
+        {
+            int q=partition(ac, p, r, bit);
+            sleep(1);
+            binaryQuickSort(ac, p, q, bit-1);
+            binaryQuickSort(ac, q+1, r, bit-1);
+        }
+    }
+
+    public static int partition(final ArrayController ac, int p, int r, int bit)
+    {
+        int i = p - 1;
+        int j = r + 1;
+    
+        while (true) {
+            // Left is not set
+            i++;
+            while(i < r && !getBit(ac.array[i], bit)) {
+                i++;
+                ac.marked.set(1, i);
+                sleep(0.45);
+                ac.comps+=2;
+            }
+            // Right is set
+            j--;
+            while(j > p && getBit(ac.array[j], bit)) {
+                j--;
+                ac.marked.set(2, j);
+                sleep(0.45);
+                ac.comps+=2;
+            }
+            // If i is less than j, we swap, otherwise we are done
+            if (i < j)
+                swap(ac, i, j);
+            else
+                return j;
+        }
+    }
+    
+    @Override
+    public String name()
+    {
+        return "Binary Quicksort";
+    }
+
+    @Override
+    public void sort(ArrayController ac)
+    {
+        int msb = analyzeBit(ac);
+        binaryQuickSort(ac, 0, ac.length-1, msb);
+    }
+}
