SortCount.java

Download 
1/*2 * SortCount.java3 *4 * Computer Science S-22, Harvard University5 */6 7import java.util.*;8 9/**10 * This class contains implementations of various array-sorting11 * algorithms.  All comparisons and moves are performed using helper12 * methods that maintain counts of these operations.  Each sort method13 * takes an array of integers.  The methods assume that all of the 14 * elements of the array should be sorted.  The algorithms sort the array15 * in place, altering the original array.16 */17public class SortCount {18    /* 19     * the integers in the test arrays are drawn from the range 20     * 0, ..., MAX_VAL 21     */22    private static int MAX_VAL = 65536;23    24    private static long compares;     // total number of comparisons25    private static long moves;        // total number of moves26    27    /*28     * compare - a wrapper that allows us to count comparisons.29     */30    private static boolean compare(boolean comparison) {31        compares++;32        return comparison;33    }34    35    /*36     * move - moves an element of the specified array to a different37     * location in the array.  move(arr, dest, source) is equivalent38     * to arr[dest] = arr[source].  Using this method allows us to39     * count the number of moves that occur.40     */41    private static void move(int[] arr, int dest, int source) {42        moves++;43        arr[dest] = arr[source];44    }45    46    /*47     * swap - swap the values of two variables.48     * Used by several of the sorting algorithms below.49     */50    private static void swap(int[] arr, int a, int b) {51        int temp = arr[a];52        arr[a] = arr[b];53        arr[b] = temp;54        moves += 3;55    }56    57    /** 58     * randomArray - creates an array of randomly generated integers59     * with the specified number of elements60     */61    public static int[] randomArray(int n) {62        int[] arr = new int[n];63        64        for (int i = 0; i < arr.length; i++) {65            arr[i] = (int)(Math.random() * (MAX_VAL + 1));66        }67        68        return arr;69    }70    71    /** 72     * almostSortedArray - creates an almost sorted array of integers73     * with the specified number of elements74     */75    public static int[] almostSortedArray(int n) {76        /* Produce a random array and sort it. */77        int[] arr = randomArray(n);78        quickSort(arr);79        80        /* 81         * Move one quarter of the elements out of place by between 182         * and 5 places.83         */84        for (int i = 0; i < n/8; i++) {85            int j = (int)(Math.random() * n);86            int displace = -5 + (int)(Math.random() * 11);87            int k = j + displace;88            if (k < 0) {89                k = 0;90            } else if (k > n - 1) {91                k = n - 1;92            }93            94            swap(arr, j, k);95        }96        97        return arr;98    }99    100    /**101     * Sets the counts of moves and comparisons to 0.102     */103    public static void initStats() {104        compares = 0;105        moves = 0;106    }107    108    /**109     * Prints the current counts of moves and comparisons.110     */111    public static void printStats() {112        int spaces = (int)(Math.log(compares)/Math.log(10));113        for (int i = 0; i < (10 - spaces); i++) {114            System.out.print(" ");115        }116        System.out.print(compares + " comparisons\t");117        118        spaces = (int)(Math.log(moves)/Math.log(10));119        for (int i = 0; i < (10 - spaces); i++) {120            System.out.print(" ");121        }122        System.out.println(moves + " moves");123    }124    125    /*126     * indexSmallest - returns the index of the smallest element127     * in the subarray from arr[start] to the end of the array.  128     * Used by selectionSort.129     */130    private static int indexSmallest(int[] arr, int start) {131        int indexMin = start;132        133        for (int i = start + 1; i < arr.length; i++) {134            if (compare(arr[i] < arr[indexMin])) {135                indexMin = i;136            }137        }138        139        return indexMin;140    }141    142    /** selectionSort */143    public static void selectionSort(int[] arr) {144        for (int i = 0; i < arr.length - 1; i++) {145            int j = indexSmallest(arr, i);146            swap(arr, i, j);147        }148    }149    150    /** insertionSort */151    public static void insertionSort(int[] arr) {152        for (int i = 1; i < arr.length; i++) {153            if (compare(arr[i] < arr[i-1])) {154                // Save a copy of the element to be inserted.155                int toInsert = arr[i];156                moves++;157                158                // Shift right to make room for element.159                int j = i;160                do {161                    move(arr, j, j - 1);162                    j = j - 1;163                } while (j > 0 && compare(toInsert < arr[j-1]));164                165                // Put the element in place.166                arr[j] = toInsert;167                moves++;168            }169        }170    }171    172    /** shellSort */173    public static void shellSort(int[] arr) {174        /*175         * Find initial increment: one less than the largest176         * power of 2 that is <= the number of objects.177         */178        int incr = 1;179        while (2 * incr <= arr.length) {180            incr = 2 * incr;181 }182        incr = incr - 1;183        184        /* Do insertion sort for each increment. */185        while (incr >= 1) {186            for (int i = incr; i < arr.length; i++) {187                if (compare(arr[i] < arr[i-incr])) {188                    int toInsert = arr[i];189                    moves++;190                    191                    int j = i;192                    do {193                        move(arr, j, j-incr);194                        j = j - incr;195                    } while (j > incr-1 && compare(toInsert < arr[j-incr]));196                    197                    arr[j] = toInsert;198                    moves++;199                }200            }201            202            // Calculate increment for next pass.203            incr = incr / 2;204        }205    }206    207    /** bubbleSort */208    public static void bubbleSort(int[] arr) {209        for (int i = arr.length - 1; i > 0; i--) {210            for (int j = 0; j < i; j++) {211                if (compare(arr[j] > arr[j+1])) {212                    swap(arr, j, j+1);213                }214            }215        }216    }217    218    /*219     * A helper method for qSort that takes the array that begins with220     * element arr[first] and ends with element arr[last] and221     * partitions it into two subarrays using the middle element of222     * the array for the pivot.  It returns the index of the last223     * element of the left subarray formed by the partition.  All224     * elements in the left subarray are <= the pivot, and all225     * elements in the right subarray are >= the pivot.226     */227    private static int partition(int[] arr, int first, int last) {228        int pivot = arr[(first + last)/2];229        moves++;   // for the above assignment230        int i = first - 1;  // index going left to right231        int j = last + 1;   // index going right to left232        233        while (true) {234            // moving from left to right, find an element >= the pivot235            do {236                i++;237            } while (compare(arr[i] < pivot));238            239            // moving from right to left, find an element <= the pivot240            do {241                j--;242            } while (compare(arr[j] > pivot)); 243            244            // If the indices still haven't met or crossed,245            // swap the elements so that they end up in the correct subarray.246            // Otherwise, the partition is complete and we return j.247            if (i < j) {248                swap(arr, i, j);249            } else {250                return j;   // index of last element in the left subarray251            }252        }                   253    }254    255    /*256     * A recursive helper method that actually implements quicksort.257     * The initial recursive call is made by quicksort() -- see below.258     */259    private static void qSort(int[] arr, int first, int last) {260        // Partition the array.  split is the index of the last261        // element of the left subarray formed by the partition.262        int split = partition(arr, first, last);263        264        //265        // Note that we only make recursive calls on subarrays that266        // have two or more elements, and thus the base case is when267        // neither subarray has two or more elements.268        //269        if (first < split) {270            qSort(arr, first, split);      // left subarray271        }272        if (last > split + 1) {273            qSort(arr, split + 1, last);   // right subarray274        }275    }276    277    /** quickSort */278    public static void quickSort(int[] arr) {279        if (arr.length <= 1) {280            return;281        }282        qSort(arr, 0, arr.length - 1); 283    }284    285    /* merge - helper method for mergesort */286    private static void merge(int[] arr, int[] temp, 287      int leftStart, int leftEnd, int rightStart, int rightEnd)288    {289        int i = leftStart;    // index into left subarray290        int j = rightStart;   // index into right subarray291        int k = leftStart;    // index into temp292        293        while (i <= leftEnd && j <= rightEnd) {294            if (compare(arr[i] < arr[j])) {295                temp[k] = arr[i];296                i++; k++;297            } else {298                temp[k] = arr[j];299                j++; k++;300            }301            moves++;302        }303        304        while (i <= leftEnd) {305            temp[k] = arr[i];306            i++; k++;307            moves++;308        }309        310        while (j <= rightEnd) {311            temp[k] = arr[j];312            j++; k++;313            moves++;314        }315        316        for (i = leftStart; i <= rightEnd; i++) {317            arr[i] = temp[i];318            moves++;319        }320    }321    322    /** mSort - recursive method for mergesort */323    private static void mSort(int[] arr, int[] temp, int start, int end) {324        if (start >= end) {325            return;326        }327        328        int middle = (start + end)/2;329        mSort(arr, temp, start, middle);330        mSort(arr, temp, middle + 1, end);331        merge(arr, temp, start, middle, middle + 1, end);332    }333    334    /** mergesort */335    public static void mergeSort(int[] arr) {336        int[] temp = new int[arr.length];337        mSort(arr, temp, 0, arr.length - 1);338    }339    340    /**341     * Prints the specified array in the following form:342     * { arr[0] arr[1] ... }343     */344    public static void printArray(int[] arr) {345        // Don't print it if it's more than 10 elements.346        if (arr.length > 10) {347            return;348        }349        350        System.out.print("{ ");351        352        for (int i = 0; i < arr.length; i++) {353            System.out.print(arr[i] + " ");354        }355        356        System.out.println("}");357    }358    359    public static void main(String args[]) {360        int[] a;       // the array361        int[] asave;   // a copy of the original unsorted array362        int numItems;363        String arrayType;364        365        /*366         * Get various parameters from the user.367         */368        Scanner in = new Scanner(System.in);369        System.out.print("How many items in the array? ");370        numItems = in.nextInt();371        in.nextLine();372        System.out.print("Random (r), almost sorted (a), or fully sorted (f)? ");373        arrayType = in.nextLine();374        System.out.println();375        in.close();376        377        /* 378         * Create the arrays. 379         */380        if (arrayType.equalsIgnoreCase("A")) {381            a = almostSortedArray(numItems);382        } else {383            a = randomArray(numItems);384            if (arrayType.equalsIgnoreCase("F")) {385                quickSort(a);386            }387        }388        asave = new int[numItems];389        System.arraycopy(a, 0, asave, 0, a.length);390        printArray(a);391        392        /*393         * Try each of the various algorithms, starting each time 394         * with a fresh copy of the initial array.395         */396        System.out.print("quickSort\t\t");397        System.arraycopy(asave, 0, a, 0, asave.length);398        initStats();399        quickSort(a);400        printStats();401        printArray(a);402        403        System.out.print("mergeSort\t\t");404        System.arraycopy(asave, 0, a, 0, asave.length);405        initStats();406        mergeSort(a);407        printStats();408        printArray(a);409        410        System.out.print("shellSort\t\t");411        System.arraycopy(asave, 0, a, 0, asave.length);412        initStats();413        shellSort(a);414        printStats();415        printArray(a);416        417        System.out.print("insertionSort\t\t");418        System.arraycopy(asave, 0, a, 0, asave.length);419        initStats();420        insertionSort(a);421        printStats();422        printArray(a);423        424        System.out.print("selectionSort\t\t");425        System.arraycopy(asave, 0, a, 0, asave.length);426        initStats();427        selectionSort(a);428        printStats();429        printArray(a);430        431        System.out.print("bubbleSort\t\t");432        System.arraycopy(asave, 0, a, 0, asave.length);433        initStats();434        bubbleSort(a);435        printStats();436        printArray(a);437    }438}