NotQuick.java

/*
Note: This is a sabotaged version of Sedgewick and Wayne's Quick.java.
http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java
This version does not shuffle the input array, allowing degenerate behaviour.

Methods not relevant to the associated assignment have been removed.
*/

import edu.princeton.cs.algs4.StdOut;

public class NotQuick {

   // This class should not be instantiated.
   private NotQuick() {
   }

   /**
    * Rearranges the array in ascending order, using the natural order.
    *
    * @param a the array to be sorted
    */
   public static void sort(Comparable[] a) {
       sort(a, 0, a.length - 1);
       assert isSorted(a);
   }

   // quicksort the subarray from a[lo] to a[hi]
   private static void sort(Comparable[] a, int lo, int hi) {
       if (hi <= lo) return;
       int j = partition(a, lo, hi);
       sort(a, lo, j - 1);
       sort(a, j + 1, hi);
       assert isSorted(a, lo, hi);
   }

   // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
   // and return the index j.
   private static int partition(Comparable[] a, int lo, int hi) {
       int i = lo;
       int j = hi + 1;
       Comparable v = a[lo];
       while (true) {

           // find item on lo to swap
           while (less(a[++i], v))
               if (i == hi) break;

           // find item on hi to swap
           while (less(v, a[--j]))
               if (j == lo) break;      // redundant since a[lo] acts as sentinel

           // check if pointers cross
           if (i >= j) break;

           exch(a, i, j);
       }

       // put partitioning item v at a[j]
       exch(a, lo, j);

       // minn kóði:

       // jöfnuð prentun
       String bil = "";
       if (lo < 10) bil = " ";
       String bil2 = "";
       if (hi < 10) bil2 = " ";
       StdOut.print("Vendisstak " + v + " raðað frá " + bil + lo + " til " + bil2 + hi + ": ");
       for (Comparable c : a) StdOut.print(c + " ");
       StdOut.println();

       // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
       return j;
   }

   /***************************************************************************
    *  Helper sorting functions.
    ***************************************************************************/

   // is v < w ?
   private static boolean less(Comparable v, Comparable w) {
       return v.compareTo(w) < 0;
   }

   // exchange a[i] and a[j]
   private static void exch(Object[] a, int i, int j) {
       Object swap = a[i];
       a[i] = a[j];
       a[j] = swap;
   }


   /***************************************************************************
    *  Check if array is sorted - useful for debugging.
    ***************************************************************************/
   private static boolean isSorted(Comparable[] a) {
       return isSorted(a, 0, a.length - 1);
   }

   private static boolean isSorted(Comparable[] a, int lo, int hi) {
       for (int i = lo + 1; i <= hi; i++)
           if (less(a[i], a[i - 1])) return false;
       return true;
   }

   // print array to standard output
   private static void show(Comparable[] comparables) {
       for (Comparable c : comparables) {
           StdOut.print(c + " ");
       }
       StdOut.println();
   }

   public static void main(String[] args) {
       String s = "QUICKBROWNFOXJUMPS";
       //String s = "KRATELEPUIMQCXOS";
       Character[] c = new Character[s.length()];
       for (int i = 0; i < s.length(); i++) {
           c[i] = s.charAt(i);
       }

       StdOut.print("Fyrir röðun: ");
       show(c);
       NotQuick.sort(c);
       assert isSorted(c);
       StdOut.print("Eftir röðun: ");
       show(c);

   }

}