Subversion Repositories programming

// Written by Ira Snyder

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 Object[] BubbleSort( Object[] 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] > a[j+1] ) arraySwap(a,j,j+1);
    }
    
    public static Object[] ImprovedBubbleSort( Object[] 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] > a[j+1] ) {
                    arraySwap(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 Object[] SelectionSort( Object[] 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] > a[m] ) m = j;
            
            //swap the "i"th element with the maximum element
            arraySwap(a,i,m);
        }
    }
    
    // method to sort the array a (passed as a parameter)
    // this will sort in O(n^2) time
    public static Object[] InsertionSort( Object[] 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
            Object 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]>ai; j-- )
                a[j] = a[j-1]; //shift down
            
            //insert ai into position a[j]
            a[j] = ai;
        }
    }
    
    //ShellSort
    //MergeSort
    //HeapSort
    //QuickSort

    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
    }
}