几种排序算法的对比

引用

Programming: Sort Testing

Your task this week is to implement four sorts, and do experiments to see how fast they run for different sizes and types of input data sets. The sorts are: selection sort, insertion sort, bubble sort and merge sort.

We're interested in two "modes" for your program:

A demonstration mode takes in a data set from the user, sorts it with each sorting algorithm, and prints out the data set at each step during each sort. In particular, it prints the entire set after each selection, each insertion, and each bubble swap. For merge sort, it describes each split into smaller subsets, and each merge into a unified subset. (Your output should match example output below.)
A comparison mode does not take a data set from the user or print out any data sets. Rather, it takes a single integer from the user, which is a set size. The program then constructs four data sets of that size: an already sorted set, a reverse-sorted set, a random set, and an "almost-sorted set" where approximately 20% of the elements are out of sort order. The program then uses all four sorts (insertion, selection, bubble, merge) to sort each of the four sets, and times how long each sort took to complete. The program then repeats the entire process for ten trials, and finds an average time for each sort, for each set type. Each of these averages (16 in all, from 160 trials) is then printed out for the user.
The usage of the program is:

$ java SortTester [1 or more integers]

If one integer is given, the program goes into comparison mode for input sets of the given size. If more than one integer is given, the program goes into demonstration mode and sorts the given set of integers.

You do not have to implement the user interface or even the code that collects and reports running-time data. That is all provided. Your only job is to fill in the actual routines that run the four sorts. However, please look over the provided code carefully so that you understand what it is doing, and why.


Please work from the following files:

SortTester.java is the driver class. It accepts and parses integer input from the user, and contains code to perform both demonstration and comparison modes. In the case of comparison mode, it generates sample sets, runs the sorts, and reports the average running times. You do not need to modify this file.
Sorters.java is the back-end that contains functions for performing the four sorts. There is one function set up for you for each sort. The functions take the form of

public static double sortType (int[] set, boolean printSteps)

The first argument, set, is the set of integers you are to sort. The second argument, printSteps, is true if the driver wants step-by-step printouts of how the function is sorting the array (i.e., demonstration mode), and false if the driver wants no printed output whatsoever (i.e., comparison mode). It is critical that if printSteps is false, no output is printed. This is because the act of printing is very, very slow, enough to dwarf the time it actually takes to sort. You will end up timing how long it takes to print, rather than how long it takes to sort.

The function returns a double of the number of milliseconds it takes to perform the sort. You do not need to figure out how to calculate the running time of the function; that is already provided in the framework. At the beginning of the function, the current system time is recorded. At the end of the function, the current system time is recorded again, and the difference between those two times is returned. Do not alter these lines, or else you may return erroneous running time results.


Once you have completed the code, perform experiments to see how long the four sorts take on different sizes and styles of input. Specifically, run your program in comparison mode for sets of 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 and 10000. Plot the results on four graphs, one for each set type. Each set type graph should contain four plots, one for each sort type. The x axis of all four graphs should be the set size, from 1000 to 10000. The y axis should be the running time in milliseconds reported by your program, from 0 to the maximum time encountered in your experiment. (All four graphs should be scaled the same on both axes.)

You may use Microsoft Excel or any other plotting program to do your graphs. Feel free to modify the formatting of the output (in SortTester.java) so that it can be easily copied into Excel -- 160 numbers is a lot to copy by hand. If you like, you can try gnuplot, a free graphing program installed on Cunix. The usage would be

$ gnuplot HW3Sorted.gp

where HW3Sorted.gp is an input file that contains instructions about how to set up the graph, as well as the actual data to plot. The output is stored in a postscript file HW3Sorted.ps. Here is a sample gnuplot file that you can modify to fit your needs. (The output file name, and file format, are set as options in that file.)

Include your graphs, in PS (postscript), TIF or PDF files, as well as the output data from which you constructed your graphs, with your submission. Name the graphs and output file(s) so it is clear which is which. Do not submit graphs in any other format.

Example Output

$ java SortTester 9 5 1 7 9 20 2 5 6
SELECTION SORT 
9 5 1 7 9 20 2 5 6 
1 5 9 7 9 20 2 5 6 
1 2 9 7 9 20 5 5 6 
1 2 5 7 9 20 5 9 6 
1 2 5 5 9 20 7 9 6 
1 2 5 5 6 20 7 9 9 
1 2 5 5 6 7 20 9 9 
1 2 5 5 6 7 9 9 20 
1 2 5 5 6 7 9 9 20 
-=-=-=-=-=-=-=- 
INSERTION 
9 5 1 7 9 20 2 5 6 
5 9 1 7 9 20 2 5 6 
1 5 9 7 9 20 2 5 6 
1 5 7 9 9 20 2 5 6 
1 5 7 9 9 20 2 5 6 
1 5 7 9 9 20 2 5 6 
1 2 5 7 9 9 20 5 6 
1 2 5 5 7 9 9 20 6 
1 2 5 5 6 7 9 9 20 
-=-=-=-=-=-=-=- 
BUBBLE 
9 5 1 7 9 20 2 5 6 
Round 1 
5 9 1 7 9 20 2 5 6 
5 1 9 7 9 20 2 5 6 
5 1 7 9 9 20 2 5 6 
5 1 7 9 9 2 20 5 6 
5 1 7 9 9 2 5 20 6 
5 1 7 9 9 2 5 6 20 
Round 2 
1 5 7 9 9 2 5 6 20 
1 5 7 9 2 9 5 6 20 
1 5 7 9 2 5 9 6 20 
1 5 7 9 2 5 6 9 20 
Round 3 
1 5 7 2 9 5 6 9 20 
1 5 7 2 5 9 6 9 20 
1 5 7 2 5 6 9 9 20 
Round 4 
1 5 2 7 5 6 9 9 20 
1 5 2 5 7 6 9 9 20 
1 5 2 5 6 7 9 9 20 
Round 5 
1 2 5 5 6 7 9 9 20 
Round 6 
No swaps. Final set: 
1 2 5 5 6 7 9 9 20 
-=-=-=-=-=-=-=- 
MERGE 
9 5 1 7 9 20 2 5 6 
Divided 9 5 1 7 9 20 2 5 6 into 9 5 1 7 and 9 20 2 5 6 
Divided 9 5 1 7 into 9 5 and 1 7 
Divided 9 5 into 9 and 5 
Merged 9 and 5 into 5 9 
Divided 1 7 into 1 and 7 
Merged 1 and 7 into 1 7 
Merged 5 9 and 1 7 into 1 5 7 9 
Divided 9 20 2 5 6 into 9 20 and 2 5 6 
Divided 9 20 into 9 and 20 
Merged 9 and 20 into 9 20 
Divided 2 5 6 into 2 and 5 6 
Divided 5 6 into 5 and 6 
Merged 5 and 6 into 5 6 
Merged 2 and 5 6 into 2 5 6 
Merged 9 20 and 2 5 6 into 2 5 6 9 20 
Merged 1 5 7 9 and 2 5 6 9 20 into 1 2 5 5 6 7 9 9 20 
1 2 5 5 6 7 9 9 20

$ java SortTester 10000 
Testing performance for sets of 10000, 10 trials... 
SELECTION SORTED 10000 130.6 
SELECTION ALMOST-SORTED 10000 130.4 
SELECTION REVERSE 10000 131.0 
SELECTION RANDOM 10000 131.0 
INSERTION SORTED 10000 0.2 
INSERTION ALMOST-SORTED 10000 25.6 
INSERTION REVERSE 10000 218.2 
INSERTION RANDOM 10000 109.5 
BUBBLE SORTED 10000 0.0 
BUBBLE ALMOST-SORTED 10000 523.9 
BUBBLE REVERSE 10000 676.1 
BUBBLE RANDOM 10000 689.3 
MERGE SORTED 10000 5.3 
MERGE ALMOST-SORTED 10000 4.2 
MERGE REVERSE 10000 3.9 
MERGE RANDOM 10000 5.2

Programming Analysis

Answer the following questions in your README (each worth 5 points):


For already sorted input, why did the running time for each sort grow as it did with respect to set size? Which sort(s) were able to efficiently recognize already-sorted input, and which continued to take quadratic time as sets grew larger? Why?

What was the ranking of your sorts from fastest to slowest for random input? Why did the slowest sorts perform slowest, and the fastest ones perform fastest? Did your results here match up with expectations?

What differences, if any, do you see between the performances of your sorts over reverse-sorted input and random input? How do you explain these differences or lack of differences?

What differences, if any, do you notice between random input and almost-sorted input? (One of your sorts should have performed surprisingly differently, where the other three performed more or less the same.) How can you explain this? What can you conclude about the suitability of different sorts for different types of input data?


Extra Credit

10 points extra credit for including two variations of Shellsort (Shellsort-A and Shellsort-B) throughout the entire programming assignment (and analysis). This will require adjusting both Java files and adding new plots to all four graphs. Shellsort-A should start with an interval of 1/2 input size and reduce the interval by half on each iteration. (Recall that Shellsort reverts to insertion sort once the interval is 1, and while sorting every "slice" as we discussed in class.) Shellsort-B should start with an interval of 1/2 input size and each iteration should reduce the interval by 2/3 (e.g., 120 goes to 40). For demonstration mode, both should first print the gap sequence they will use, then, for each interval in the gap sequence, each slice, before and after sorting that slice, and then the complete list after the slices are reassembled. (You do not need to print the details of insertion sort for each individual slice). Be sure to test on lists with duplicate elements! (You can modify the driver code, SortTester, to create such lists to test on.) What differences do you see between the performance of Shellsort-A and Shellsort-B, if any? How do you explain these differences by the interval reduction strategy? Do you notice anything unusual if the input size is a power of 2? (Recall our discussion of Shell's gap sequence, which goes by powers of 2.)

10 points extra credit for including four variations of quicksort (quicksort-A through quicksort-D) throughout the entire programming assignment (and analysis). This will require adjusting both Java files and adding new plots to all four graphs. Quicksort-A should use the middle element as the pivot; quicksort-B should use median-of-three pivot selection; quicksort-C should use median-of-five, and quicksort-D should (update) use the actual median element (i.e., scan the entire list and calculate the optimal pivot). For demonstration mode, each recursive call to quicksort should print the original list, the pivot selected, each pair of elements that are swapped, and the final list, with a clear distinction between left partition, pivot and right partition. Be sure to test on lists with duplicate elements! (You can modify the driver code, SortTester, to create such lists to test on.) How does quicksort match up against the other sorts, mergesort in particular? For each type of input set, how did pivot selection affect quicksort running time? How do you explain these differences? (Note: quicksort-A may crash on Cunix for large data sets due to running out of memory. Don't panic if this happens. Document the set size where quicksort runs out of memeory, and include quicksort-A on your graph only up until that set size.)

SortTester.java:

import java.util.Random;

/**
 * Sort-tester driver class for 3134 S08 HW3. DKE, 2/2008
 */
public class SortTester {

    /**
     * Constructor receives command-line arguments.
     */
    public SortTester(String[] args) throws Exception {

        // At least one argument required.
        if (args.length < 1) {
            throw new Exception(
                    "SortTester must be run with at least 1 integer argument.");
        }

        if (args.length == 1) {

            // If the user gave one argument it is assumed to be a set
            // size for comparison mode.
            comparison(Integer.parseInt(args[0]));
        } else {

            // Otherwise, the multiple arguments are assumed to be
            // a set for demonstration mode.
            demonstration(args);
        }

    }

    /**
     * Main function constructs a SortTester object.
     */
    public static void main(String[] args) throws Exception {
        try {
            new SortTester(args);
        } catch (Exception e) {
            //System.err.println(e.getMessage());
            e.printStackTrace();
        }
    }

    /**
     * Sort the set provided the user. Demonstrate how the various sets work.
     */
    public void demonstration(String[] stringSet) throws Exception {

        int[] set;

        /**
         * Prepare an array of ints that is the same size as the array of
         * strings given at the command line.
         */
        set = new int[stringSet.length];

        // Convert the strings to ints..
        // For each string in the input set...
        for (int i = 0; i < stringSet.length; i++) {

            String token = stringSet[i];

            try {
                // Convert the string to int.
                set[i] = Integer.parseInt(token);
            } catch (NumberFormatException e) {
                throw new Exception("Bad integer in position " + (i + 1) + ": "
                        + token);
            }
        }

        System.out.println("Ready to sort " + set.length + " integers.");

        // Run selection sort
        Sorters.selectionSort(makeCopy(set), true);

        // Run insertion sort
        Sorters.insertionSort(makeCopy(set), true);

        // Run bubble sort
        Sorters.bubbleSort(makeCopy(set), true);

        // Run merge sort
        Sorters.mergeSort(makeCopy(set), true);

        // Run Shellsort-A
        Sorters.shellSortA(makeCopy(set), true);
        
        // Run Shellsort-B
        Sorters.shellSortB(makeCopy(set), true);
        
        // Run Quicksort-A
        Sorters.quickSortA(makeCopy(set), true);
        
        // Run Quicksort-B
        Sorters.quickSortB(makeCopy(set), true);
        
        // Run Quicksort-C
        Sorters.quickSortC(makeCopy(set), true);
        
        // Run Quicksort-D
        Sorters.quickSortD(makeCopy(set), true);
    }

    public static int[] makeCopy(int[] set) {

        int[] result = new int[set.length];
        for (int i = 0; i < set.length; i++) {
            result[i] = set[i];
        }
        return result;
    }

    /**
     * Run each the sorts 10 times on a user-given set size and report the
     * average time it took for each sort to run.
     */
    public void comparison(int setSize) throws Exception {

        // Number of trials
        int trials = 10;
        // Matrix stores the times for each experiment
        // First [] stores the sort type, from 0 to 9
        // Second [] stores the set type, from 0 to 3
        double[][] times = new double[10][4];

        int[] set;

        System.out.println("Testing performance for sets of " + setSize + ", "
                + trials + " trials...");

        // For each trial...
        for (int i = 0; i < trials; i++) {

            // Make a sorted set and do selection sort
            set = makeSortedSet(setSize);
            times[0][0] += Sorters.selectionSort(set, false);

            // Make a sorted set and do insertion sort
            set = makeSortedSet(setSize);
            times[1][0] += Sorters.insertionSort(set, false);

            // Make a sorted set and do bubble sort
            set = makeSortedSet(setSize);
            times[2][0] += Sorters.bubbleSort(set, false);

            // Make an sorted set and do merge sort
            set = makeSortedSet(setSize);
            times[3][0] += Sorters.mergeSort(set, false);
            
            // Make an sorted set and do Shellsort-A
            set = makeSortedSet(setSize);
            times[4][0] += Sorters.shellSortA(set, false);
            
            // Make an sorted set and do Shellsort-B
            set = makeSortedSet(setSize);
            times[5][0] += Sorters.shellSortB(set, false);
            
            // Make an sorted set and do Quicksort-A
            set = makeSortedSet(setSize);
            times[6][0] += Sorters.quickSortA(set, false);
            
            // Make an sorted set and do Quicksort-B
            set = makeSortedSet(setSize);
            times[7][0] += Sorters.quickSortB(set, false);
            
            // Make an sorted set and do Quicksort-C
            set = makeSortedSet(setSize);
            times[8][0] += Sorters.quickSortC(set, false);
            
            // Make an sorted set and do Quicksort-D
            set = makeSortedSet(setSize);
            times[9][0] += Sorters.quickSortD(set, false);

            // Make an almost sorted set and do selection sort
            set = makeAlmostSortedSet(setSize);
            times[0][1] += Sorters.selectionSort(set, false);

            // Make an almost sorted set and do insertion sort
            set = makeAlmostSortedSet(setSize);
            times[1][1] += Sorters.insertionSort(set, false);

            // Make an almost sorted set and do bubble sort
            set = makeAlmostSortedSet(setSize);
            times[2][1] += Sorters.bubbleSort(set, false);

            // Make an almost sorted set and do merge sort
            set = makeAlmostSortedSet(setSize);
            times[3][1] += Sorters.mergeSort(set, false);
            
            // Make an almost sorted set and do Shellsort-A
            set = makeAlmostSortedSet(setSize);
            times[4][1] += Sorters.shellSortA(set, false);
            
            // Make an almost sorted set and do Shellsort-B
            set = makeAlmostSortedSet(setSize);
            times[5][1] += Sorters.shellSortB(set, false);
            
            // Make an almost sorted set and do Quicksort-A
            set = makeAlmostSortedSet(setSize);
            times[6][1] += Sorters.quickSortA(set, false);
            
            // Make an almost sorted set and do Quicksort-B
            set = makeAlmostSortedSet(setSize);
            times[7][1] += Sorters.quickSortB(set, false);
            
            // Make an almost sorted set and do Quicksort-C
            set = makeAlmostSortedSet(setSize);
            times[8][1] += Sorters.quickSortC(set, false);
            
            // Make an almost sorted set and do Quicksort-D
            set = makeAlmostSortedSet(setSize);
            times[9][1] += Sorters.quickSortD(set, false);

            // Make a reverse sorted set and do selection sort
            set = makeReverseSet(setSize);
            times[0][2] += Sorters.selectionSort(set, false);

            // Make a reverse sorted set and do insertion sort
            set = makeReverseSet(setSize);
            times[1][2] += Sorters.insertionSort(set, false);

            // Make a reverse sorted set and do bubble sort
            set = makeReverseSet(setSize);
            times[2][2] += Sorters.bubbleSort(set, false);

            // Make a reverse sorted set and do merge sort
            set = makeReverseSet(setSize);
            times[3][2] += Sorters.mergeSort(set, false);
            
            // Make an reverse sorted set and do Shellsort-A
            set = makeReverseSet(setSize);
            times[4][2] += Sorters.shellSortA(set, false);
            
            // Make an reverse sorted set and do Shellsort-B
            set = makeReverseSet(setSize);
            times[5][2] += Sorters.shellSortB(set, false);
            
            // Make an reverse sorted set and do Quicksort-A
            set = makeReverseSet(setSize);
            times[6][2] += Sorters.quickSortA(set, false);
            
            // Make an reverse sorted set and do Quicksort-B
            set = makeReverseSet(setSize);
            times[7][2] += Sorters.quickSortB(set, false);
            
            // Make an reverse sorted set and do Quicksort-C
            set = makeReverseSet(setSize);
            times[8][2] += Sorters.quickSortC(set, false);
            
            // Make an reverse sorted set and do Quicksort-D
            set = makeReverseSet(setSize);
            times[9][2] += Sorters.quickSortD(set, false);

            // Make a random set and do selection sort
            set = makeRandomSet(setSize);
            times[0][3] += Sorters.selectionSort(set, false);

            // Make a random set and do insertion sort
            set = makeRandomSet(setSize);
            times[1][3] += Sorters.insertionSort(set, false);

            // Make a random set and do bubble sort
            set = makeRandomSet(setSize);
            times[2][3] += Sorters.bubbleSort(set, false);

            // Make a random set and do merge sort
            set = makeRandomSet(setSize);
            times[3][3] += Sorters.mergeSort(set, false);
            
            // Make an random set and do Shellsort-A
            set = makeRandomSet(setSize);
            times[4][3] += Sorters.shellSortA(set, false);
            
            // Make an random set and do Shellsort-B
            set = makeRandomSet(setSize);
            times[5][3] += Sorters.shellSortB(set, false);
            
            // Make an random set and do Quicksort-A
            set = makeRandomSet(setSize);
            times[6][3] += Sorters.quickSortA(set, false);
            
            // Make an random set and do Quicksort-B
            set = makeRandomSet(setSize);
            times[7][3] += Sorters.quickSortB(set, false);
            
            // Make an random set and do Quicksort-C
            set = makeRandomSet(setSize);
            times[8][3] += Sorters.quickSortC(set, false);
            
            // Make an random set and do Quicksort-D
            set = makeRandomSet(setSize);
            times[9][3] += Sorters.quickSortD(set, false);
        }

        // Now we need to compile and print the results.
        // For each sort type...
        for (int sortType = 0; sortType < 10; sortType++) {

            // Choose the string that represents the sort type
            String sortTypeString;
            if (sortType == 0) {
                sortTypeString = "SELECTION";
            } else if (sortType == 1) {
                sortTypeString = "INSERTION";
            } else if (sortType == 2) {
                sortTypeString = "BUBBLE";
            } else if (sortType == 3) {
                sortTypeString = "MERGE";
            } else if (sortType == 4) {
                sortTypeString = "SHELLSORT-A";
            } else if (sortType == 5) {
                sortTypeString = "SHELLSORT-B";
            } else if (sortType == 6) {
                sortTypeString = "QUICKSORT-A";
            } else if (sortType == 7) {
                sortTypeString = "QUICKSORT-B";
            } else if (sortType == 8) {
                sortTypeString = "QUICKSORT-C";
            } else {
                sortTypeString = "QUICKSORT-D";
            }

            // For each set type..
            for (int setType = 0; setType < 4; setType++) {

                // Find the AVERAGE time among the trials by dividing the
                // running sum by the number of trials
                times[sortType][setType] /= trials;

                // Choose the string that represents the set type
                String setTypeString;
                if (setType == 0) {
                    setTypeString = "SORTED";
                } else if (setType == 1) {
                    setTypeString = "ALMOST-SORTED";
                } else if (setType == 2) {
                    setTypeString = "REVERSE";
                } else {
                    setTypeString = "RANDOM";
                }

                // Print the results
                System.out.println(sortTypeString + " " + setTypeString + " "
                        + setSize + " " + times[sortType][setType]);

            }
        }

    }

    /**
     * Make a sorted set of integers.
     */
    public static int[] makeSortedSet(int size) {

        int[] result = new int[size];

        for (int i = 0; i < size; i++) {
            result[i] = i + 1;
        }

        return result;
    }

    /**
     * Make an almost-sorted set of integers.
     */
    public static int[] makeAlmostSortedSet(int size) {

        int[] result = new int[size];

        for (int i = 0; i < size; i++) {
            result[i] = i + 1;
        }

        Random r = new Random();

        // Swap one-fifth of the elements with other elements
        for (int i = 0; i < (size / 10); i++) {

            // Pick two random elements and swap them
            int firstToSwap = r.nextInt(size);
            int secondToSwap = r.nextInt(size);

            int crossover = result[firstToSwap];
            result[firstToSwap] = result[secondToSwap];
            result[secondToSwap] = crossover;
        }

        return result;
    }

    /**
     * Make a reverse-sorted set of integers.
     */
    public static int[] makeReverseSet(int size) {

        int[] result = new int[size];

        for (int i = 0; i < size; i++) {
            result[i] = size - i;
        }

        return result;
    }

    /**
     * Make a random set of integers.
     */
    public static int[] makeRandomSet(int size) {

        Random r = new Random();

        int[] result = new int[size];

        for (int i = 0; i < size; i++) {
            result[i] = r.nextInt();
        }

        return result;
    }
}

Sorters.java:

/**
 * Back-end class for 3134 HW3. This is the one you edit.
 */
public class Sorters {

    /**
     * Run selection sort on a set.
     */
    public static double selectionSort(int[] set, boolean printSteps) {

        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("SELECTION SORT");
            System.out.println(printList(set));
        }

        // DO SELECTION SORT HERE!
        // Print progress if printSteps is set to true.
        int length = set.length;
        for (int i = 0; i < length - 1; ++i) {
            int minIdx = i;
            for (int j = i + 1; j < length; ++j) {
                if (set[minIdx] > set[j]) {
                    minIdx = j;
                }
            }
            swap(set, i, set, minIdx);

            // print progress
            if (printSteps) {
                System.out.println(printList(set));
            }
        }

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    /**
     * Run insertion sort on a set.
     */
    public static double insertionSort(int[] set, boolean printSteps) {

        // Mark the start time.
        double startTime = System.currentTimeMillis();

        insertionSort(set, 0, set.length - 1, printSteps);

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    /**
     * Internal method shared by insertion sort and Quicksort methods.
     * 
     * @param set
     * @param left
     * @param right
     * @param printSteps
     */
    private static void insertionSort(int[] set, int left, int right,
            boolean printSteps) {

        int length = right - left + 1;

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("INSERTION");
            System.out.println(printList(set, left, length));
            ;
        }

        // DO INSERTION SORT HERE!
        // Print progress if printSteps is set to true.
        int j = 0;

        for (int i = left + 1; i <= right; ++i) {
            // avoids explicit swap
            int min = set[i];
            for (j = i; (j > left) && (set[j - 1] > min); --j) {
                set[j] = set[j - 1];
            }
            set[j] = min;

            // print progress
            if (printSteps) {
                System.out.println(printList(set, left, length));
            }
        }

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println("-=-=-=-=-=-=-=-");
        }
    }

    /**
     * Run bubble sort on a set.
     */
    public static double bubbleSort(int[] set, boolean printSteps) {

        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("BUBBLE");
            System.out.println(printList(set));
        }

        // DO BUBBLE SORT HERE!
        // Print progress if printSteps is set to true.
        int length = set.length;
        for (int round = 1; round < length; ++round) {
            boolean hasSwap = false;
            if (printSteps) {
                System.out.println("Round " + round);
            }
            for (int j = 0; j < length - round; ++j) {
                if (set[j] > set[j + 1]) {
                    swap(set, j, set, j + 1);
                    hasSwap = true;
                    if (printSteps) {
                        System.out.println(printList(set));
                    }
                }
            }

            // the array is already sorted, end loop
            if (!hasSwap) {
                break;
            }
        }

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println("No swaps.  Final set:");
            System.out.println(printList(set));
            ;
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;

    }

    /**
     * Run merge sort on a set.
     */
    public static double mergeSort(int[] set, boolean printSteps) {

        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("MERGE");
            System.out.println(printList(set));
        }

        // DO MERGE SORT HERE!
        // (You will need to call other functions, recursively)
        // Print progress if printSteps is set to true.
        int length = set.length;
        int[] copy = new int[length];
        mergeSort(set, copy, 0, length - 1, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    /**
     * Internal method that makes resursive calls.
     * 
     * @param array
     *            the original array to sort.
     * @param tempArray
     *            an array to place the merged result.
     * @param left
     *            the left-most index of the subarray.
     * @param right
     *            the right-most index of the subarray.
     * @param printSteps
     *            whether to print sort progress.
     */
    private static void mergeSort(int[] array, int[] tempArray, int left,
            int right, boolean printSteps) {
        if (left < right) {
            int center = (left + right) / 2;
            if (printSteps) {
                System.out.print("Divided ");
                System.out.print(printList(array, left, right - left + 1));
                System.out.print(" into ");
                System.out.print(printList(array, left, center - left + 1));
                System.out.print(" and ");
                System.out
                        .println(printList(array, center + 1, right - center));
            }
            mergeSort(array, tempArray, left, center, printSteps);
            mergeSort(array, tempArray, center + 1, right, printSteps);
            merge(array, tempArray, left, center + 1, right, printSteps);
        }
    }

    /**
     * Internal method to merge two sorted halves of a subarray.
     * 
     * @param array
     *            the original array to sort.
     * @param tempArray
     *            an array to place the merged result.
     * @param leftIdx
     *            the left-most index of the subarray.
     * @param rightIdx
     *            the index of the start of the second half.
     * @param rightEnd
     *            the right-most index of the subarray.
     * @param printSteps
     *            whether to print sort progress.
     */
    private static void merge(int[] array, int[] tempArray, int leftIdx,
            int rightIdx, int rightEnd, boolean printSteps) {
        int leftEnd = rightIdx - 1;
        int tempIdx = leftIdx;
        int tempIdx2 = tempIdx;
        int numElements = rightEnd - leftIdx + 1;

        if (printSteps) {
            System.out.print("Merged ");
            System.out.print(printList(array, leftIdx, leftEnd - leftIdx + 1));
            System.out.print(" and ");
            System.out
                    .print(printList(array, rightIdx, rightEnd - rightIdx + 1));
        }

        // main loop
        while (leftIdx <= leftEnd && rightIdx <= rightEnd) {
            if (array[leftIdx] < array[rightIdx]) {
                tempArray[tempIdx++] = array[leftIdx++];
            } else {
                tempArray[tempIdx++] = array[rightIdx++];
            }
        }

        // copy rest of left half
        while (leftIdx <= leftEnd) {
            tempArray[tempIdx++] = array[leftIdx++];
        }

        // copy rest of right half
        while (rightIdx <= rightEnd) {
            tempArray[tempIdx++] = array[rightIdx++];
        }

        if (printSteps) {
            System.out.print(" into ");
            System.out.println(printList(tempArray, tempIdx2, tempIdx
                    - tempIdx2));
        }

        // copy tempArray back
        for (int i = 0; i < numElements; ++i, --rightEnd) {
            array[rightEnd] = tempArray[rightEnd];
        }
    }

    /**
     * Run Shellsort-A on a set.
     */
    public static double shellSortA(int[] set, boolean printSteps) {

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("SHELLSORT-A");
            System.out.println(printList(set));
        }

        // DO SHELLSORT-A HERE!
        // Print progress if printSteps is set to true.
        double result = shellSort(set, 1.0 / 2.0, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        return result;
    }

    /**
     * Run Shellsort-B on a set.
     */
    public static double shellSortB(int[] set, boolean printSteps) {

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("SHELLSORT-B");
            System.out.println(printList(set));
        }

        // DO SHELLSORT-B HERE!
        // Print progress if printSteps is set to true.
        double result = shellSort(set, 1.0 / 3.0, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        return result;
    }

    /**
     * Internal method, run Shellsort on a set.
     */
    private static double shellSort(int[] set, double reductionRatio,
            boolean printSteps) {

        // Mark the start time.
        double startTime = System.currentTimeMillis();

        int length = set.length;

        // print gap sequence
        if (printSteps) {
            System.out.print("GAP SEQUENCE:");
            for (int gap = length / 2; gap > 0; gap *= reductionRatio) {
                System.out.print(" " + gap);
            }
            System.out.println();
        }

        for (int gap = length / 2; gap > 0; gap *= reductionRatio) {

            // print the slices before sort in current interval
            if (printSteps) {
                System.out.println("Gap: " + gap);
                for (int i = 0; i < gap; ++i) {
                    if (printSteps) {
                        System.out.print("Slice before:");
                        for (int j = i; j < length; j += gap) {
                            System.out.print(" " + set[j]);
                        }
                        System.out.println();
                    }
                }
            }

            // sort the slices
            for (int i = gap; i < length; ++i) {

                // avoids explicit swap
                int temp = set[i];
                int j = i;

                for (; (j >= gap) && (temp < set[j - gap]); j -= gap) {
                    set[j] = set[j - gap];
                }
                set[j] = temp;
            }

            // print the slices after sort in current interval
            if (printSteps) {
                for (int i = 0; i < gap; ++i) {
                    if (printSteps) {
                        System.out.print("Slice after:");
                        for (int j = i; j < length; j += gap) {
                            System.out.print(" " + set[j]);
                        }
                        System.out.println();
                    }
                }
            }
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    private static final int CUTOFF = 10;

    public static double quickSortA(int[] set, boolean printSteps) {
        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("QUICKSORT-A");
            System.out.println(printList(set));
        }

        // DO QUICKSORT-A HERE!
        // Print progress if printSteps is set to true.
        _quickSortA(set, 0, set.length - 1, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    private static void _quickSortA(int[] set, int left, int right,
            boolean printSteps) {
        if (printSteps) {
            System.out.println("List: " + printList(set));
        }

        if (left + CUTOFF <= right) {
            // select pivot
            int center = (left + right) / 2;
            int pivot = set[center];
            if (printSteps) {
                System.out.println("Pivot: " + pivot);
            }

            // place pivot at position right
            set[center] = set[right];
            set[right] = pivot;

            // Begin partitioning
            int i = left - 1;
            int j = right;
            while (true) {
                while (set[++i] < pivot) { }
                while ((j > left) && (set[--j] > pivot)) { }
                if (i < j) {
                    if (printSteps) {
                        System.out.println("Pair to swap: " + set[i] + ", "
                                + set[j]);
                    }
                    swap(set, i, set, j);
                } else {
                    break;
                }
            }

            if (printSteps) {
                System.out.println("Pair to swap: " + set[i] + ", "
                        + set[right]);
            }
            swap(set, i, set, right); // Restore pivot

            _quickSortA(set, left, i - 1, printSteps); // Sort small elements
            _quickSortA(set, i + 1, right, printSteps); // Sort large elements
        } else {
            insertionSort(set, left, right, false);
        }
    }

    public static double quickSortB(int[] set, boolean printSteps) {
        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("QUICKSORT-B");
            System.out.println(printList(set));
        }

        // DO QUICKSORT-B HERE!
        // Print progress if printSteps is set to true.
        _quickSortB(set, 0, set.length - 1, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    private static void _quickSortB(int[] set, int left, int right,
            boolean printSteps) {
        if (printSteps) {
            System.out.println("List: " + printList(set));
        }

        if (left + CUTOFF <= right) {
            // median3 implicitly places pivot at position right-1
            int pivot = median3(set, left, right);
            if (printSteps) {
                System.out.println("Pivot: " + pivot);
            }

            // begin partitioning
            int i = left;
            int j = right - 1;

            while (true) {
                while (set[++i] < pivot) { }
                while (set[--j] > pivot) { }
                if (i < j) {
                    if (printSteps) {
                        System.out.println("Pair to swap: " + set[i] + ", "
                                + set[j]);
                    }
                    swap(set, i, set, j);
                } else {
                    break;
                }
            }

            if (printSteps) {
                System.out.println("Pair to swap: " + set[i] + ", "
                        + set[right - 1]);
            }
            swap(set, i, set, right - 1); // restore pivot

            _quickSortB(set, left, i - 1, printSteps);
            _quickSortB(set, i + 1, right, printSteps);
        } else {
            insertionSort(set, left, right, false);
        }
    }

    public static double quickSortC(int[] set, boolean printSteps) {
        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("QUICKSORT-C");
            System.out.println(printList(set));
        }

        // DO QUICKSORT-C HERE!
        // Print progress if printSteps is set to true.
        _quickSortC(set, 0, set.length - 1, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    private static void _quickSortC(int[] set, int left, int right,
            boolean printSteps) {
        if (printSteps) {
            System.out.println("List: " + printList(set));
        }

        if (left + CUTOFF <= right) {
            // median5 implicitly places pivot at position right-1
            int pivot = median5(set, left, right);
            if (printSteps) {
                System.out.println("Pivot: " + pivot);
            }

            // begin partitioning
            int i = left;
            int j = right - 1;

            while (true) {
                while (set[++i] < pivot) { }
                while (set[--j] > pivot) { }
                if (i < j) {
                    if (printSteps) {
                        System.out.println("Pair to swap: " + set[i] + ", "
                                + set[j]);
                    }
                    swap(set, i, set, j);
                } else {
                    break;
                }
            }

            if (printSteps) {
                System.out.println("Pair to swap: " + set[i] + ", "
                        + set[right - 1]);
            }
            swap(set, i, set, right - 1); // restore pivot

            _quickSortC(set, left, i - 1, printSteps);
            _quickSortC(set, i + 1, right, printSteps);
        } else {
            insertionSort(set, left, right, false);
        }
    }

    public static double quickSortD(int[] set, boolean printSteps) {
        // Mark the start time.
        double startTime = System.currentTimeMillis();

        // Print the input set if we are asked to.
        if (printSteps) {
            System.out.println("QUICKSORT-D");
            System.out.println(printList(set));
        }

        // DO QUICKSORT-D HERE!
        // Print progress if printSteps is set to true.
        _quickSortD(set, 0, set.length - 1, printSteps);

        // Print the output set if we are asked to.
        if (printSteps) {
            System.out.println(printList(set));
            System.out.println("-=-=-=-=-=-=-=-");
        }

        // Mark the finish time and return the time it took to sort.
        return System.currentTimeMillis() - startTime;
    }

    private static void _quickSortD(int[] set, int left, int right,
            boolean printSteps) {
        if (printSteps) {
            System.out.println("List: " + printList(set));
        }

        if (left + CUTOFF <= right) {
            // use quick select to find the actual median as pivot
            // the pivot is placed at position center
            int pivot = quickSelectMedian(set, left, right, printSteps);
            if (printSteps) {
                System.out.println("Pivot: " + pivot);
            }

            // place pivot at position right
            int center = left + (right - left) / 2;
            set[center] = set[right];
            set[right] = pivot;

            // Begin partitioning
            int i = left - 1;
            int j = right;
            while (true) {
                while (set[++i] < pivot) { }
                while ((j > left) && (set[--j] > pivot)) { }
                if (i < j) {
                    if (printSteps) {
                        System.out.println("Pair to swap: " + set[i] + ", "
                                + set[j]);
                    }
                    swap(set, i, set, j);
                } else {
                    break;
                }
            }

            if (printSteps) {
                System.out.println("Pair to swap: " + set[i] + ", "
                        + set[right]);
            }
            swap(set, i, set, right); // Restore pivot

            _quickSortD(set, left, i - 1, printSteps); // Sort small elements
            _quickSortD(set, i + 1, right, printSteps); // Sort large elements
        } else {
            insertionSort(set, left, right, false);
        }
    }

    private static int median3(int[] set, int left, int right) {
        int center = (left + right) / 2;

        // sort the subarray of left-center-right
        if (set[center] < set[left]) {
            swap(set, left, set, center);
        }
        if (set[right] < set[left]) {
            swap(set, left, set, right);
        }
        if (set[right] < set[center]) {
            swap(set, center, set, right);
        }

        // place pivot at position right-1
        swap(set, center, set, right - 1);
        return set[right - 1];
    }

    // a hack to reduce memory allocation time
    private static int[] _tempArrayForMedian5 = new int[5];

    private static int median5(int[] set, int left, int right) {
        int center = (left + right) / 2;
        int leftCenter = (left + center) / 2;
        int rightCenter = (center + right) / 2;

        // sort the subarray of
        // left-leftCenter-center-rightCenter-rightCenter
        _tempArrayForMedian5[0] = set[left];
        _tempArrayForMedian5[1] = set[leftCenter];
        _tempArrayForMedian5[2] = set[center];
        _tempArrayForMedian5[3] = set[rightCenter];
        _tempArrayForMedian5[4] = set[right];
        insertionSort(_tempArrayForMedian5, false);

        // copy the sort results back to the input array
        // and place the pivot at position right-1
        set[left] = _tempArrayForMedian5[0];
        set[leftCenter] = _tempArrayForMedian5[1];
        set[center] = set[right - 1];
        set[right - 1] = _tempArrayForMedian5[2];
        set[rightCenter] = _tempArrayForMedian5[3];
        set[right] = _tempArrayForMedian5[4];

        return set[right - 1];
    }

    public static int quickSelectMedian(int[] set, int left, int right,
            boolean printSteps) {
        int k = (right - left) / 2 + 1; // expected median's index as k
        quickSelect(set, left, right, k, printSteps);
        return set[left + k - 1];
    }

    /**
     * Internal selection method that makes recursive calls. Uses
     * median-of-three partitioning and a cutoff of 10. Places the kth smallest
     * item in set[k-1]. NOTE: This method will modify the input array's order.
     * 
     * @param set
     *            the input array of int.
     * @param left
     *            the left-most index of the subarray.
     * @param right
     *            the right-most index of the subarray.
     * @param k
     *            the desired rank (1 is minimum) in the entire array.
     */
    private static void quickSelect(int[] set, int left, int right, int k,
            boolean printSteps) {
        if (left + CUTOFF <= right) {
            int pivot = median3(set, left, right);

            // begin partitioning
            int i = left;
            int j = right - 1;
            while (true) {
                while (set[++i] < pivot) { }
                while (set[--j] > pivot) { }
                if (i < j) {
                    if (printSteps) {
                        System.out.println("Pair to swap: " + set[i] + ", "
                                + set[j]);
                    }
                    swap(set, i, set, j);
                } else {
                    break;
                }
            }

            if (printSteps) {
                System.out.println("Pair to swap: " + set[i] + ", "
                        + set[right - 1]);
            }
            swap(set, i, set, right - 1); // restore pivot

            if (k - 1 < i) {
                quickSelect(set, left, i - 1, k, printSteps);
            } else if (k - 1 > i) {
                quickSelect(set, i + 1, right, k, printSteps);
            }
        } else {
            // do an insertion sort on the subarray
            insertionSort(set, left, right, false);
        }
    }

    /**
     * Return a rendering of a list as a StringBuffer. You can pass the buffer
     * to a System.out.println() to actually print the set.
     */
    private static StringBuffer printList(int[] set) {
        return printList(set, 0, set.length);
    }

    private static StringBuffer printList(int[] set, int beginIdx, int length) {
        StringBuffer result = new StringBuffer();

        for (int i = 0; i < length; i++) {
            result.append(set[beginIdx++]);

            // Add spaces between elements
            if (i < (length - 1)) {
                result.append(" ");
            }
        }

        return result;
    }

    private static final void swap(int[] src, int srcIdx, int[] dst, int dstIdx) {
        int temp = src[srcIdx];
        src[srcIdx] = dst[dstIdx];
        dst[dstIdx] = temp;
    }
}

AutomateSortComparisonReport.java: see attached file.

Uses JFreeChart 1.0.1 for charting. Visit http://www.jfree.org/jfreechart/ for more information on JFreeChart.

Sample plot graphs of this project can be found here: http://rednaxelafx.iteye.com/blog/174063

评论

1 楼 beyondqinghua 2008-03-25  

有时间慢慢看,收藏先!