java - 用于计算未正确输出的算法的比较和执行时间的代码

Question

在我的java作业中，我必须计算发生的比较次数，以及选择排序、插入排序、冒泡排序、快速排序和合并排序算法的总执行时间。下面的代码是一个驱动程序，用于测试运行算法的代码，同时计算它们的执行时间和比较。在代码中，我用值初始化了列表并通过它们运行它。我得到的唯一输出是“排序列表...”，这只是第一行。其余部分没有运行，我迷路了。请帮忙。

public class SortingTest {

    //create 3 constant values
    static final int SIZE = 1000;//number of values in the lists
    static final int SORTED_ORDER = 0;//for sorted lists
    static final int RANDOM_ORDER = 1;//for unsorted lists

    //create the lists for each sorting algorithm
    static Integer[] selArr = new Integer[SIZE];
    static Integer[] insArr = new Integer[SIZE];
    static Integer[] bubArr = new Integer[SIZE];
    static Integer[] quiArr = new Integer[SIZE];
    static Integer[] merArr = new Integer[SIZE];

    public static void main(String[] args) {
        //perform the sorting on sorted lists
        performSorting(SORTED_ORDER);

        //perform the sorting on unsorted lists
        performSorting(RANDOM_ORDER);

        //perform the sorting on unsorted lists
        performSorting(RANDOM_ORDER);

    }

    private static void performSorting(int order) {
        if(order == SORTED_ORDER)//display if the lists are in sorted order or not
            System.out.println("Sorted Lists...");
        else 
            System.out.println("Unsorted Lists...");

            //initialize the lists in sorted order
            initLists(order);

            //initialize the number of comparisons and total execution time
            initComparisonsAndExecutionTime();

            //sort the lists
            sortLists();

            //display the number of comparisons and total execution time
            printComparisonsAndExecutionTime();
        }


    //initializes the lists with the same values
    private static void initLists(int order) {
        int number;
        for(int i=0;i<SIZE;i++) {
            if(order == SORTED_ORDER)
                number = new Integer(i);
            else
                number = new Integer((int)(Math.random()*SIZE));

            selArr[i] = number;
            insArr[i] = number;
            bubArr[i] = number;
            quiArr[i] = number;
            merArr[i] = number;
        }
    }

    /*initializes the number
    of comparisons and total execution time for each algorithm*/
    private static void initComparisonsAndExecutionTime() {
        Sorting.selectionSortComparisons = 0;
        Sorting.insertionSortComparisons = 0;
        Sorting.bubbleSortComparisons = 0;
        Sorting.quickSortComparisons = 0;
        Sorting.mergeSortComparisons = 0;
        Sorting.selectionSortExecutionTime = 0L;
        Sorting.insertionSortExecutionTime = 0L;
        Sorting.bubbleSortExecutionTime = 0L;
        Sorting.quickSortExecutionTime = 0L;
        Sorting.mergeSortExecutionTime = 0L;
    }

    /*calls each sorting algorithm with the 
    corresponding lists to sort the values*/
    private static void sortLists() {
        Sorting.selectionSort(selArr);
        Sorting.insertionSort(insArr);
        Sorting.bubbleSort(bubArr);
        Sorting.quickSort(quiArr);
        Sorting.mergeSort(merArr);
    }

    /*displays the number of comparisons and total execution time
    for each algorithm*/
    private static void printComparisonsAndExecutionTime() {
        System.out.println("----------------------");

        System.out.printf("%-15s%15s%15s\n", "SORTING METHOD",
                          "COMPARISONS", "EXEC.TIME(ns)");

        System.out.println("----------------------");

        System.out.printf("%-15s%15d%15d\n", "Selection sort",
                          Sorting.selectionSortComparisons,
                          Sorting.selectionSortExecutionTime);

        System.out.printf("%-15s%15d%15d\n", "Insertion sort",
                          Sorting.insertionSortComparisons,
                          Sorting.insertionSortExecutionTime);

        System.out.printf("%-15s%15d%15d\n", "Bubble sort",
                          Sorting.bubbleSortComparisons,
                          Sorting.bubbleSortExecutionTime);

        System.out.printf("%-15s%15d%15d\n", "Quick sort",
                          Sorting.quickSortComparisons,
                          Sorting.quickSortExecutionTime);

        System.out.printf("%-15s%15d%15d\n", "Merge sort",
                          Sorting.mergeSortComparisons,
                          Sorting.mergeSortExecutionTime);

        System.out.println("-----------------------\n\n");
    }
}

这是所有算法的实现

    public class Sorting 
   {

public static int selectionSortComparisons = 0;
public static int insertionSortComparisons = 0;
public static int bubbleSortComparisons = 0;
public static int quickSortComparisons = 0;
public static int mergeSortComparisons = 0;
public static long selectionSortExecutionTime = 0L;
public static long insertionSortExecutionTime = 0L;
public static long bubbleSortExecutionTime = 0L;
public static long quickSortExecutionTime = 0L;
public static long mergeSortExecutionTime = 0L;

/**
 * Sorts the specified array of integers using the selection
 * sort algorithm.
 *
 * @param data the array to be sorted
 */

public static <T extends Comparable<T>> 
    void selectionSort(T[] data)
{
    long startTime = System.nanoTime();//stores the beginning time of 
selection sort algorithm
    int min;
    T temp;

    for (int index = 0; index < data.length-1; index++)
    {
        min = index;
        for (int scan = index+1; scan < data.length; scan++) {
            selectionSortComparisons++;//counts the number of 
comparisons in selection sort
            if (data[scan].compareTo(data[min])<0)
                min = scan;
              }


        swap(data, min, index);
        }
    long endTime = System.nanoTime();//stores the ending time of 
selection sort
    selectionSortExecutionTime = endTime - startTime;//computes total 
execution time of selection sort
    }

/**
 * Swaps to elements in an array. Used by various sorting algorithms.
 * 
 * @param data   the array in which the elements are swapped
 * @param index1 the index of the first element to be swapped
 * @param index2 the index of the second element to be swapped
 */
private static <T extends Comparable<T>> 
    void swap(T[] data, int index1, int index2)
{
    T temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;
}

/**
 * Sorts the specified array of objects using an insertion
 * sort algorithm.
 *
 * @param data the array to be sorted
 */
public static <T extends Comparable<T>> 
    void insertionSort(T[] data)
{
    long startTime = System.nanoTime();//stores beginning time of 
insertion sort
    for (int index = 1; index < data.length; index++)
    {
        T key = data[index];
        int position = index;

        // shift larger values to the right 
        while (position > 0 && data[position-1].compareTo(key) > 0)
        {
            insertionSortComparisons++;//counts the number of 
comparisons in insertion sort
            data[position] = data[position-1];
            position--;
        }
        if (position > 0)
            insertionSortComparisons++;//counts the number of comparisons in insertion sort

        data[position] = key;
    }
    long endTime = System.nanoTime();//stores ending time of insertion 
 sort
    selectionSortExecutionTime = endTime - startTime;//computes total execution time of selection sort
}

/**
 * Sorts the specified array of objects using a bubble sort
 * algorithm.
 *
 * @param data the array to be sorted
 */
public static <T extends Comparable<T>> 
    void bubbleSort(T[] data)
{
    long startTime = System.nanoTime();//stores the beginning of bubble sort
    int position, scan;
    T temp;

    for (position =  data.length - 1; position >= 0; position--)
    {
        for (scan = 0; scan <= position - 1; scan++)
        {
            bubbleSortComparisons++;//counts the number of comparisons in bubble sort
            if (data[scan].compareTo(data[scan+1]) > 0)
                swap(data, scan, scan + 1);
        }
    }
    long endTime = System.nanoTime();//stores end of bubble sort
    selectionSortExecutionTime = endTime - startTime;//computes total execution time of bubble sort
}

/**
 * Sorts the specified array of objects using the merge sort
 * algorithm.
 *
 * @param data the array to be sorted
 */
public static <T extends Comparable<T>>
    void mergeSort(T[] data)
{
    long startTime = System.nanoTime();//stores beginning of merge sort
    mergeSort(data, 0, data.length - 1);
    long endTime = System.nanoTime();//stores end of merge sort
    selectionSortExecutionTime = endTime - startTime;//computes total execution time of merge sort
}

/**
 * Recursively sorts a range of objects in the specified array using the
 * merge sort algorithm.
 *
 * @param data the array to be sorted
 * @param min  the index of the first element 
 * @param max  the index of the last element
 */
private static <T extends Comparable<T>>
    void mergeSort(T[] data, int min, int max)
{
    if (min < max)
    {
        int mid = (min + max) / 2;
        mergeSort(data, min, mid);
        mergeSort(data, mid+1, max);
        merge(data, min, mid, max);
    }
}

/**
 * Merges two sorted subarrays of the specified array.
 *
 * @param data the array to be sorted
 * @param first the beginning index of the first subarray 
 * @param mid the ending index fo the first subarray
 * @param last the ending index of the second subarray
 */
@SuppressWarnings("unchecked")
private static <T extends Comparable<T>>
    void merge(T[] data, int first, int mid, int last)
{
    T[] temp = (T[])(new Comparable[data.length]);

    int first1 = first, last1 = mid;  // endpoints of first subarray
    int first2 = mid+1, last2 = last;  // endpoints of second subarray
    int index = first1;  // next index open in temp array

    //  Copy smaller item from each subarray into temp until one
    //  of the subarrays is exhausted
    while (first1 <= last1 && first2 <= last2)
    {
        mergeSortComparisons++;//count the number of comparisons in merge sort
        if (data[first1].compareTo(data[first2]) < 0)
        {
            temp[index] = data[first1];
            first1++;
        }
        else
        {
            temp[index] = data[first2];
            first2++;
        }
        index++;
    }

    //  Copy remaining elements from first subarray, if any
    while (first1 <= last1)
    {
        temp[index] = data[first1];
        first1++;
        index++;
    }

    //  Copy remaining elements from second subarray, if any
    while (first2 <= last2)
    {
        temp[index] = data[first2];
        first2++;
        index++;
    }

    //  Copy merged data into original array
    for (index = first; index <= last; index++)
        data[index] = temp[index];

}

/**
 * Sorts the specified array of objects using the quick sort algorithm.
 * 
 * @param data the array to be sorted
 */
public static <T extends Comparable<T>> 
    void quickSort(T[] data)
{
    long startTime = System.nanoTime();//stores beginning of quick sort
    quickSort(data, 0, data.length - 1);
    long endTime = System.nanoTime();//stores end of quick sort
    selectionSortExecutionTime = endTime - startTime;//computes total execution time of quick sort
    }

/**
 * Recursively sorts a range of objects in the specified array using the
 * quick sort algorithm. 
 * 
 * @param data the array to be sorted
 * @param min  the minimum index in the range to be sorted
 * @param max  the maximum index in the range to be sorted
 */
private static <T extends Comparable<T>> 
    void quickSort(T[] data, int min, int max)
{
    if (min < max)
    {
        // create partitions
        int indexofpartition = partition(data, min, max);

        // sort the left partition (lower values)
        quickSort(data, min, indexofpartition - 1);

        // sort the right partition (higher values)
        quickSort(data, indexofpartition + 1, max);
    }
}

/**
 * Used by the quick sort algorithm to find the partition.
 * 
 * @param data the array to be sorted
 * @param min  the minimum index in the range to be sorted
 * @param max  the maximum index in the range to be sorted
 */
private static <T extends Comparable<T>> 
    int partition(T[] data, int min, int max)
{
    T partitionelement;
    int left, right;
    int middle = (min + max) / 2;

    // use the middle data value as the partition element
    partitionelement = data[middle];
    // move it out of the way for now
    swap(data, middle, min);

    left = min;
    right = max;

    while (left < right)
    {
        // search for an element that is > the partition element
        while (left < right && data[left].compareTo(partitionelement) <= 0)
            quickSortComparisons++;//counts the number of comparisons in quick sort
            left++;

        // search for an element that is < the partition element
        while (data[right].compareTo(partitionelement) > 0)
            quickSortComparisons++;//counts the number of comparisons in quick sort
            right--;

        quickSortComparisons++;//counts the number of comparisons in quick sort
        // swap the elements
        if (left < right)
            quickSortComparisons++;//counts the number of comparisons in quick sort
            swap(data, left, right);
    }

    // move the partition element into place
    swap(data, min, right);

    return right;
}
}

Answer 1

我尝试添加一些打印来帮助调试您的代码。我发现你的快速排序方法陷入了无限循环。

输出是:

Sorted Lists...
Lists Initialized!
Comparisons and Exec time initialized!
Selection done!
Insertion done!
Bubble done!

当我评论这一行时Sorting.quickSort(quiArr); ，我得到以下输出:

----------------------
SORTING METHOD     COMPARISONS  EXEC.TIME(ns)
----------------------
Selection sort          499500        2726141
Insertion sort          243586              0
Bubble sort             499500              0
Quick sort                   0              0
Merge sort                8697              0
-----------------------    

这让我检查了您的代码以设置每种排序方法的执行时间。看起来所有方法都设置了 Sorting.selectionSortExecutionTime ，正如您在以下 mergeSort 代码片段中看到的那样:

public static <T extends Comparable<T>> void mergeSort(T[] data) {
        long startTime = System.nanoTime();// stores
                            // beginning
                            // of
                            // merge
                            // sort
        mergeSort(data, 0, data.length - 1);
        long endTime = System.nanoTime();// stores
                            // end
                            // of
                            // merge
                            // sort
        /* Wrong variable */
        selectionSortExecutionTime = endTime - startTime;// computes
                                // total
                                // execution
                                // time
                                // of
                                // merge
                                // sort
}

我在快速排序方法中进行了一些调试，发现如下:while 在 while(left<right) 内循环没有花括号，所以 left++和right--省略的地方，只有 quickSortComparisons++在他们里面。这是固定代码，其中的注释指出了我所描述的内容:

private static <T extends Comparable<T>> int partition(T[] data,
        int min,
        int max) {
    T partitionelement;
    int left, right;
    int middle = (min + max) / 2;
    // use the middle data value as the
    // partition element
    partitionelement = data[middle];
    // move it out of the way for now
    swap(data, middle, min);
    left = min;
    right = max;
    while (left < right) {
        // search for an element that is >
        // the partition element
        while (left < right
                && data[left].compareTo(partitionelement) <= 0){
            // counts the number of comparisons in quick sort
            quickSortComparisons++;
            left++; // <--- this was not in the while loop
        }
        quickSortComparisons++; // <--- I believe you should have this one too
        // search for an element that is <
        // the partition element
        while (data[right].compareTo(partitionelement) > 0){
            // counts the number of comparisons in quick sort
            quickSortComparisons++;
            right--; // <--- this wasn't in the while loop neither
        }
        // counts the number of comparisons in quick sort
        quickSortComparisons++;
        // swap the elements
        if (left < right)
            quickSortComparisons++;// counts the number of comparisons in quick sort
        swap(data, left, right);
    }
    // move the partition element into place
    swap(data, min, right);
    return right;
} 

希望我有帮助!