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

    }

}