Subversion Repositories programming

// Written by Ira Snyder
// Project #5

import java.io.*;

class SortMethods {
    
    // method to sort the array a (passed as a parameter)
    // this will sort in O(n^2) time
    public static void BubbleSort( Comparable[] a ) {
        //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);
    }
    // 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;
            
            for( int j=0; j<i; j++ )
                if( a[j].compareTo(a[j+1]) > 0 ) {
                    Test.swap(a,j,j+1);
                    inorder=false;
                }
            if(inorder) break;  //array sorted, so bail out
        }
    }
    
    // method to sort the array a (passed as a paramter)
    // this will sort in O(n^2) time
    public static void SelectionSort( Comparable[] a ) {
        //loop from the back of the array moving towards the front
        for( int i=a.length-1; i>0; i-- ) {
            //placeholder for the maximum element
            int m=0;
            //find the maximum element in the array
            for( int j=1; j<=i; j++ )
                if( a[j].compareTo(a[m]) > 0 ) m = j;
            
            //swap the "i"th element with the maximum element
            Test.swap(a,i,m);
        }
    }
    
    // method to sort the array a (passed as a parameter)
    // this will sort in O(n^2) time
    public static void InsertionSort( Comparable[] a ) {
        //iterate through the array from the beginning to the end
        for ( int i=1; i<a.length; i++ ) {
            //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-- ) {
                a[j] = a[j-1]; //shift down
                Test.incSwapCount();
            }
            
            //insert ai into position a[j]
            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]; Test.incSwapCount();
                j -= d;
            }
            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 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
    private static void MergeSortHelper( Comparable[] a, int p, int q ) {
        if (q-p < 2) return;
        int m = (p+q)/2;
        MergeSortHelper(a, p, m);
        MergeSortHelper(a, m, q);
        merge(a, p, m, q);
    }

    // PRECONDITIONS: a[p..m-1] and a[m..q-1] are in ascending order;
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
    private static void merge( Comparable[] a, int p, int m, int q ) {
        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++]; Test.incSwapCount(); }
            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);
        }
        
        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 i = (a.length-1)/2; i >= 0; i-- )
            heapify(a, i, a.length);
        
        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; Test.incSwapCount();
    }
    
    //
    public static void QuickSort( Comparable[] a ) {
        //call the real quicksort with the needed parameters
        QuickSortHelper(a,0,a.length);
    }

    // PRECONDITION: 0 <= p <= q <= a.length
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
    private static void QuickSortHelper( Comparable[] a, int p, int q ) {
        if (q-p < 2) return;
        int j = partition(a, p, q);
        QuickSortHelper(a, p, j);
        QuickSortHelper(a, j+1, q);
    }

    // RETURNS: index j of pivot element a[j];
    // POSTCONDITION: a[i] <= a[j] <= a[k] for p <= i <= j <= k < q;
    private static int partition( Comparable[] a, int p, int q ) {
        Comparable pivot = a[p];
        int i = p, j = q;
        
        while( i < j ) {
            while( j > i && a[--j].compareTo(pivot) >= 0 )
            ;  // empty loop
            
            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]; Test.incSwapCount(); }
        }
        
        a[j] = pivot; Test.incSwapCount();
        return j;
    }
    
    public static void arraySwap( Object[] a, int posA, int posB ) {
        Object temp = a[posB]; // temp = B
        a[posB] = a[posA];     // B = A
        a[posA] = temp;        // A = temp
    }
}