Sort.java

Download 
1/*2 * Sort.java3 *4 * Computer Science S-22, Harvard University5 */6 7/**8 * Sort - a class containing implementations of various array-sorting9 * algorithms.  Each method takes an array of ints.  The methods10 * assume that the array is full.  They sort the array in place,11 * altering the original array.12 */13public class Sort {14    public static final int NUM_ELEMENTS = 10;15    16    /*17     * swap - swap the values of arr[a] and arr[b].18     * Used by several of the sorting algorithms below.19     */20    private static void swap(int[] arr, int a, int b) {21        int temp = arr[a];22        arr[a] = arr[b];23        arr[b] = temp;24    }25    26    /*27     * indexSmallest - returns the index of the smallest element28     * in the subarray from arr[start] to the end of the array.  29     * Used by selectionSort.30     */31    private static int indexSmallest(int[] arr, int start) {32        int indexMin = start;33        34        for (int i = start + 1; i < arr.length; i++) {35            if (arr[i] < arr[indexMin]) {36                indexMin = i;37            }38        }39        40        return indexMin;41    }42    43    /** selectionSort */44    public static void selectionSort(int[] arr) {45        for (int i = 0; i < arr.length - 1; i++) {46            int j = indexSmallest(arr, i);47            swap(arr, i, j);48        }49    }50    51    /** insertionSort */52    public static void insertionSort(int[] arr) {53        for (int i = 1; i < arr.length; i++) {54            if (arr[i] < arr[i-1]) {55                // Save a copy of the element to be inserted.56                int toInsert = arr[i];57                58                // Shift right to make room for element.59                int j = i;60                do {61                    arr[j] = arr[j - 1];62                    j = j - 1;63                } while (j > 0 && toInsert < arr[j-1]);64                65                // Put the element in place.66                arr[j] = toInsert;67            }68        }69    }70    71    /** shellSort */72    public static void shellSort(int[] arr) {73        /*74         * Find initial increment: one less than the largest75         * power of 2 that is <= the number of objects.76         */77        int incr = 1;78        while (2 * incr <= arr.length) {79            incr = 2 * incr;80        }81        incr = incr - 1;82        83        /* Do insertion sort for each increment. */84        while (incr >= 1) {85            for (int i = incr; i < arr.length; i++) {86                if (arr[i] < arr[i-incr]) {87                    int toInsert = arr[i];88                    89                    int j = i;90                    do {91                        arr[j] = arr[j - incr];92                        j = j - incr;93                    } while (j > incr-1 &&94                             toInsert < arr[j-incr]);95                    96                    arr[j] = toInsert;97                }98            }99            100            // Calculate increment for next pass.101            incr = incr / 2;102        }103    }104    105    /** bubbleSort */106    public static void bubbleSort(int[] arr) {107        for (int i = arr.length - 1; i > 0; i--) {108            for (int j = 0; j < i; j++) {109                if (arr[j] > arr[j+1]) {110                    swap(arr, j, j+1);111                }112            }113        }114    }115    116    /* partition - helper method for qSort */117    public static int partition(int[] arr, int first, int last) {118        int pivot = arr[(first + last)/2];119        int i = first - 1;  // index going left to right120        int j = last + 1;   // index going right to left121        122        while (true) {123            // moving from left to right, find an element >= the pivot124            do {125                i++;126            } while (arr[i] < pivot);127            128            // moving from right to left, find an element <= the pivot129            do {130                j--;131            } while (arr[j] > pivot); 132            133            // If the indices still haven't met or crossed,134            // swap the elements so that they end up in the correct subarray.135            // Otherwise, the partition is complete and we return j.136            if (i < j) {137                swap(arr, i, j);138            } else {139                return j;     // index of last element in the left subarray140            }141        }142    }143    144    /* qSort - recursive method that does the work for quickSort */145    private static void qSort(int[] arr, int first, int last) {146        int split = partition(arr, first, last);147        148        if (first < split) {149            qSort(arr, first, split);      // left subarray150        }151        if (last > split + 1) {152            qSort(arr, split + 1, last);   // right subarray153        }154    }155    156    /** quicksort */157    public static void quickSort(int[] arr) {158        if (arr.length <= 1) {159            return;160        }161        qSort(arr, 0, arr.length - 1); 162    }163    164    /* merge - helper method for mergesort */165    private static void merge(int[] arr, int[] temp, 166                              int leftStart, int leftEnd, int rightStart, int rightEnd)167    {168        int i = leftStart;    // index into left subarray169        int j = rightStart;   // index into right subarray170        int k = leftStart;    // index into temp171        172        while (i <= leftEnd && j <= rightEnd) {173            if (arr[i] < arr[j]) {174                temp[k] = arr[i];175                i++; k++;176            } else {177                temp[k] = arr[j];178                j++; k++;179            }180        }181        182        while (i <= leftEnd) {183            temp[k] = arr[i];184            i++; k++;185        }186        while (j <= rightEnd) {187            temp[k] = arr[j];188            j++; k++;189        }190        191        for (i = leftStart; i <= rightEnd; i++) {192            arr[i] = temp[i];193        }194    }195    196    /** mSort - recursive method for mergesort */197    private static void mSort(int[] arr, int[] temp, int start, int end) {198        if (start >= end) {199            return;200        }201        202        int middle = (start + end)/2;203        mSort(arr, temp, start, middle);204        mSort(arr, temp, middle + 1, end);205        merge(arr, temp, start, middle, middle + 1, end);206    }207    208    /** mergesort */209    public static void mergeSort(int[] arr) {210        int[] temp = new int[arr.length];211        mSort(arr, temp, 0, arr.length - 1);212    }213    214    /**215     * printArray - prints the specified array in the following form:216     * { arr[0] arr[1] ... }217     */218    public static void printArray(int[] arr) {219        System.out.print("{ ");220        221        for (int i = 0; i < arr.length; i++) {222            System.out.print(arr[i] + " ");223        }224        225        System.out.println("}");226    }227    228    public static void main(String[] arr) { 229        int[] orig = new int[NUM_ELEMENTS];230        for (int i = 0; i < NUM_ELEMENTS; i++) {231            orig[i] = (int)(50 * Math.random());232        }233        printArray(orig);234        235        int[] copy = new int[NUM_ELEMENTS];236        237        /* selection sort */238        System.arraycopy(orig, 0, copy, 0, orig.length); 239        selectionSort(copy);240        System.out.print("selection sort:\t");241        printArray(copy);242        243        /* insertion sort */244        System.arraycopy(orig, 0, copy, 0, orig.length); 245        insertionSort(copy);246        System.out.print("insertion sort:\t");247        printArray(copy);248        249        /* Shell sort */250        System.arraycopy(orig, 0, copy, 0, orig.length); 251        shellSort(copy);252        System.out.print("Shell sort:\t");253        printArray(copy);254        255        /* bubble sort */256        System.arraycopy(orig, 0, copy, 0, orig.length); 257        bubbleSort(copy);258        System.out.print("bubble sort:\t");259        printArray(copy);260        261        /* quicksort */262        System.arraycopy(orig, 0, copy, 0, orig.length); 263        quickSort(copy);264        System.out.print("quicksort:\t");265        printArray(copy);266        267        /* mergesort */268        System.arraycopy(orig, 0, copy, 0, orig.length); 269        mergeSort(copy);270        System.out.print("mergesort:\t");271        printArray(copy);272    }273}