tejasomina

ShellSort.java

Oct 21st, 2020
498
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import org.apache.commons.lang3.ArrayUtils;
  2.  
  3. public class ShellSort {
  4.     static void print(Comparable[] a) {
  5.         for (Comparable i : a) System.out.print(i + " ");
  6.         System.out.println();
  7.     }
  8.  
  9.     static void swap(Comparable[] a, int p, int q) {
  10.         Comparable temp = a[p];
  11.         a[p] = a[q];
  12.         a[q] = temp;
  13.     }
  14.  
  15.     static boolean less(Comparable a, Comparable b) {
  16.         return a.compareTo(b) < 0;
  17.     }
  18.  
  19.     public static boolean isSorted(Comparable[] a) {
  20.         for (int i = 1; i < a.length; i++) {
  21.             if (less(a[i], a[i - 1])) return false;
  22.         }
  23.         return true;
  24.     }
  25.  
  26.     public static void sort(Comparable[] a) {
  27.         int n = a.length;
  28.         int h = 1;
  29.         while (h < n / 3) h = 3 * h + 1; // Gives highest 3x+1 value for given N
  30.         while (h >= 1) {
  31.             System.out.println(h+"-sorting the array!");
  32.             for (int i = 1; i < n; i++) {
  33.                 for (int j = i; j >= h; j -= h)
  34.                     if (less(a[j], a[j - h])){
  35.                         swap(a, j, j - h);
  36.                         print(a);
  37.                     }
  38.                     else break;
  39.             }
  40.             h = h / 3;
  41.         }
  42.  
  43.     }
  44.  
  45.     public static void main(String[] args) {
  46.         String s = "SHELLSORTEXAMPLE";
  47.         Character[] a = ArrayUtils.toObject(s.toCharArray());
  48. //        Integer[] a = new Integer[]{31, 41, 59, 26, 41, 58};
  49.         print(a);
  50.         sort(a);
  51.         if (!isSorted(a)) throw new AssertionError("Array not sorted");
  52.         print(a);
  53.     }
  54. }
  55.  
RAW Paste Data