Merge pull request TheAlgorithms#287 from sandeeproy99/patch-3

Christian Bender · web-flow · commit 1f76cda0e815 · 2018-04-08T19:53:08.000+02:00
CombSort.java
diff --git a/Sorts/CombSort.java b/Sorts/CombSort.java
@@ -0,0 +1,62 @@
+// Java program for implementation of Comb Sort
+
+class CombSort
+{
+    // To find gap between elements
+    static int getNextGap(int gap)
+    {
+        // Shrink gap by Shrink factor
+        gap = (gap*10)/13;
+        gap = (gap < 1) ? 1: gap;
+    }
+ 
+    // Function to sort arr[] using Comb Sort
+    static void sort(int arr[])
+    {
+        int n = arr.length;
+ 
+        // initialize gap
+        int gap = n;
+ 
+        // Initialize swapped as true to make sure that loop runs
+        boolean swapped = true;
+ 
+        // Keep running while gap is more than 1 and last iteration caused a swap
+        while (gap != 1 || swapped)
+        {
+            // Find next gap
+            gap = getNextGap(gap);
+ 
+            // Initialize swapped as false so that we can check if swap happened or not
+            swapped = false;
+ 
+            // Compare all elements with current gap
+            for (int i=0; i<n-gap; i++)
+            {
+                if (arr[i] > arr[i+gap])
+                {
+                    // Swap arr[i] and arr[i+gap]
+                    int temp = arr[i];
+                    arr[i] = arr[i+gap];
+                    arr[i+gap] = temp;
+ 
+                    // Set swapped
+                    swapped = true;
+                }
+            }
+        }
+    }
+ 
+    // Driver method
+    public static void main(String args[])
+    {
+        CombSort ob = new CombSort();
+        int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
+        ob.sort(arr);
+ 
+        System.out.println("sorted array");
+        for (int i=0; i<arr.length; ++i) {
+            System.out.print(arr[i] + " ");
+        } 
+    }
+}
