Subversion Repositories programming

// Written by Ira Snyder

// Project #5

// License: Public Domain (added 07-11-2005)

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

    }

}