WebSVN – programming – Diff – /cs241/p5/SortMethods.java

 // Written by Ira Snyder
+// Project #5
 import java.io.*;
 class SortMethods {
         //loop from the back of the array moving towards the beginning
         for( int i=a.length-1; i>0; i-- )
             //loop from the beginning of the array to position "i"
             for( int j=0; j<i; j++ )
                 //compare elements next to each other, and swap if necessary
-                if( a[j].compareTo( a[j+1] ) > 0 ) Test.swap(a,j,j+1);
+                if( a[j].compareTo(a[j+1]) > 0 ) Test.swap(a,j,j+1);
+    }
+    // method to sort the array a
+    // this is the same as the regular bubble sort, but it ends
+    // early if the array is sorted
     public static void ImprovedBubbleSort( Comparable[] a ) {
         boolean inorder=true;
         for( int i=a.length-1; i>0; i-- ) {
             inorder=true;
             //store a[i] in a temp location
             Comparable ai = a[i];
             int j=i; //start for the inner loop
             //find the place to insert ai, and shift elements down
-            for ( j=i; j>0 && a[j-1].compareTo(ai) > 0; j-- )
+            for ( j=i; j>0 && a[j-1].compareTo(ai) > 0; j-- ) {
                 a[j] = a[j-1]; //shift down
+                Test.incSwapCount();
+            }
             //insert ai into position a[j]
-            a[j] = ai;
+            a[j] = ai; Test.incSwapCount();
+        }
+    }
+    // an insertion sort that skips elements as it sorts
     private static void SkipInsertionSort( Comparable[] a, int c, int d ) {
         for( int i = c+d; i < a.length; i+=d ) {
             Comparable ai = a[i];
             int j = i;
             while( j > c && a[j-d].compareTo(ai) > 0 ) {
-                a[j] = a[j-d];
+                a[j] = a[j-d]; Test.incSwapCount();
                 j -= d;
+            }
-            a[j] = ai;
+            a[j] = ai; Test.incSwapCount();
+        }
+    }
+    // this sorts like a comb, with the interval shrinking as
+    // we progress in the sort
     public static void ShellSort( Comparable[] a ) {
         for( int d = a.length/2; d > 0; d /= 2 )
             for( int c = 0; c < d; c++ )
                 //applies Insertion sort to the skip sequence
                 SkipInsertionSort(a, c, d);
+    }
+    // sorts by breaking the array into small pieces, then sorting
+    // the smaller lists in the same fashion until the small lists
+    // are only length=1, which is sorted by default
     public static void MergeSort( Comparable[] a ) {
-        //call mergesort on the whole array
+        //call the real mergesort on the whole array
         MergeSortHelper(a,0,a.length);
+    }
     // PRECONDITION: 0 <= p <= q <= a.length
     // POSTCONDITION: a[p..q-1] is in ascending order
         if( a[m-1].compareTo(a[m]) <= 0 ) return;  // a[p..q-1] is already sorted
         int i = p, j = m, k = 0;
         Comparable[] aa = new Comparable[q-p];
         while (i < m && j < q)
-            if( a[i].compareTo(a[j]) < 0 ) aa[k++] = a[i++];
+            if( a[i].compareTo(a[j]) < 0 ) { aa[k++] = a[i++]; Test.incSwapCount(); }
-            else aa[k++] = a[j++];
+            else { aa[k++] = a[j++]; Test.incSwapCount(); }
+        if (i < m) {
+            System.arraycopy(a, i, a, p+k, m-i);  // shift a[i..m-1]
+            Test.incSwapCount(m-i);
+        }
-        if (i < m) System.arraycopy(a, i, a, p+k, m-i);  // shift a[i..m-1]
         System.arraycopy(aa, 0, a, p, k);  // copy aa[0..k-1] to a[p..p+k-1];
+        Test.incSwapCount(k);
+    }
     // PRECONDITION: 0 <= p <= q <= a.length
     // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
     public static void HeapSort( Comparable[] a ) {
         for( int j = a.length-1; j > 0; j-- ) {
             Test.swap(a, 0, j);
             heapify(a, 0, j);
+        }
+    }
+    //Postcondition: The array a is a Heap
     private static void heapify( Comparable[] a, int i, int n ) {
         Comparable ai = a[i];
         while( i < n/2 ) {                       // a[i] is not a leaf
             int j = 2*i+1;                       // a[j] is ai¿s left child
             if( j+1 < n && a[j+1].compareTo(a[j]) > 0 ) ++j;  // a[j] is ai's larger child
             if( a[j].compareTo(ai) <= 0 ) break;              // a[j] is not out of order
             a[i] = a[j];                         // promote a[j]
+            Test.incSwapCount();
             i = j;                               // move down to the next level
+        }
-        a[i] = ai;
+        a[i] = ai; Test.incSwapCount();
+    }
+    //
     public static void QuickSort( Comparable[] a ) {
         //call the real quicksort with the needed parameters
         QuickSortHelper(a,0,a.length);
+    }
         while( i < j ) {
             while( j > i && a[--j].compareTo(pivot) >= 0 )
             ;  // empty loop
-            if( j > i ) { a[i] = a[j]; }
+            if( j > i ) { a[i] = a[j]; Test.incSwapCount(); }
             while( i < j && a[++i].compareTo(pivot) <= 0 )
             ;  // empty loop
-            if( i < j ) { a[j] = a[i]; }
+            if( i < j ) { a[j] = a[i]; Test.incSwapCount(); }
+        }
-        a[j] = pivot;
+        a[j] = pivot; Test.incSwapCount();
         return j;
+    }
     public static void arraySwap( Object[] a, int posA, int posB ) {
         Object temp = a[posB]; // temp = B

Subversion Repositories programming

(root)/cs241/p5/SortMethods.java @ 57 – Rev 55 → 57