Refactored BubbleSort, CycleSort, CocktailShakerSort

nikitap492 · nikitap492 · commit 52d1182de588 · 2018-04-09T15:48:08.000+03:00
diff --git a/Sorts/CocktailShakerSort.java b/Sorts/CocktailShakerSort.java
diff --git a/Sorts/src/sort/BubbleSort.java b/Sorts/src/sort/BubbleSort.java
@@ -1,7 +1,6 @@
 package sort;
 
-import static sort.SortUtils.print;
-import static sort.SortUtils.swap;
+import static sort.SortUtils.*;
 
 /**
  *
@@ -27,10 +26,8 @@ public  <T extends Comparable<T>> T[] sort(T array[]) {
         do {
             swap = false;
             for (int count = 0; count < last-1; count++) {
-                int comp = array[count].compareTo(array[count + 1]);
-                if (comp > 0) {
-                    swap(array, count, count + 1);
-                    swap = true;
+                if (less(array[count], array[count + 1])) {
+                    swap = swap(array, count, count + 1);
                 }
             }
             last--;
@@ -42,7 +39,7 @@ public  <T extends Comparable<T>> T[] sort(T array[]) {
     public static void main(String[] args) {
 
         // Integer Input
-        Integer[] integers = {4,23,6,78,1,54,231,9,12};
+        Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};
         BubbleSort bubbleSort = new BubbleSort();
         bubbleSort.sort(integers);
 
diff --git a/Sorts/src/sort/CocktailShakerSort.java b/Sorts/src/sort/CocktailShakerSort.java
@@ -0,0 +1,70 @@
+package sort;
+
+import static sort.SortUtils.*;
+
+/**
+ *
+ * @author Mateus Bizzo (https://github.com/MattBizzo)
+ * @author Podshivalov Nikita (https://github.com/nikitap492)
+ *
+ */
+
+class CocktailShakerSort implements SortAlgorithm {
+
+	/**
+	 * This method implements the Generic Cocktail Shaker Sort
+	 *
+	 * @param array The array to be sorted
+	 * Sorts the array in increasing order
+	 **/
+
+	@Override
+	public <T extends Comparable<T>> T[] sort(T[] array){
+
+		int last = array.length;
+		
+		// Sorting
+		boolean swap;
+		do {
+			swap = false;
+			
+			//front
+			for (int count = 0; count <= last - 2; count++) {
+				if (less(array[count + 1], array[count])) {
+					swap = swap(array, count, count + 1);
+				}
+			}
+			//break if no swap occurred
+			if (!swap) {
+				break;
+			}
+			swap = false;
+			
+			//back
+			for (int count = last - 2; count >= 0; count--) {
+				if (less(array[count + 1], array[count])) {
+					swap = swap(array, count, count + 1);
+				}
+			}
+			last--;
+		//end
+		} while (swap);
+		return array;
+	}
+
+	// Driver Program
+	public static void main(String[] args) {
+		// Integer Input
+		Integer[] integers = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };
+		CocktailShakerSort shakerSort = new CocktailShakerSort();
+
+		// Output => 1 4 6 9 12 23 54 78 231
+		print(shakerSort.sort(integers));
+
+		// String Input
+		String[] strings = { "c", "a", "e", "b", "d" };
+		print(shakerSort.sort(strings));
+	}
+
+
+}
diff --git a/Sorts/src/sort/CycleSort.java b/Sorts/src/sort/CycleSort.java
@@ -0,0 +1,81 @@
+package sort;
+
+import static sort.SortUtils.less;
+import static sort.SortUtils.print;
+
+/**
+ *  @author Podshivalov Nikita (https://github.com/nikitap492)
+ */
+class CycleSort implements SortAlgorithm {
+
+
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] arr) {
+        int n = arr.length;
+
+        // traverse array elements
+        for (int j = 0; j <= n - 2; j++) {
+            // initialize item as starting point
+            T item = arr[j];
+
+            // Find position where we put the item.
+            int pos = j;
+            for (int i = j + 1; i < n; i++)
+                if (less(arr[i], item)) pos++;
+
+            // If item is already in correct position
+            if (pos == j)  continue;
+
+            // ignore all duplicate elements
+            while (item.compareTo(arr[pos]) == 0)
+                pos += 1;
+
+            // put the item to it's right position
+            if (pos != j) {
+                item = replace(arr, pos, item);
+            }
+
+            // Rotate rest of the cycle
+            while (pos != j) {
+                pos = j;
+
+                // Find position where we put the element
+                for (int i = j + 1; i < n; i++)
+                    if (less(arr[i], item)){
+                        pos += 1;
+                    }
+
+
+                // ignore all duplicate elements
+                while (item.compareTo(arr[pos]) == 0)
+                    pos += 1;
+
+                // put the item to it's right position
+                if (item != arr[pos]) {
+                    item = replace(arr, pos, item);
+                }
+            }
+        }
+
+        return arr;
+    }
+
+    private <T extends Comparable<T>> T replace(T[] arr, int pos, T item){
+        T temp = item;
+        item = arr[pos];
+        arr[pos] = temp;
+        return item;
+    }
+
+
+
+    public static void main(String[] args) {
+        Integer arr[] = { 4, 23, 6, 78, 1, 26, 11, 23 , 0, -6, 3, 54, 231, 9, 12 };
+        CycleSort cycleSort = new CycleSort();
+        cycleSort.sort(arr);
+
+        System.out.println("After sort : ");
+        print(arr);
+    }
+
+}
diff --git a/Sorts/src/sort/SortUtils.java b/Sorts/src/sort/SortUtils.java
@@ -18,10 +18,11 @@ final class SortUtils {
      * @param idx index of the first element
      * @param idy index of the second element
      */
-    static <T> void swap(T[] array, int idx, int idy){
+    static <T> boolean swap(T[] array, int idx, int idy){
         T swap = array[idx];
         array[idx] = array[idy];
         array[idy] = swap;
+        return true;
     }
 
 
