-3

对于带有第一个元素枢轴的快速排序,我得到了奇怪的计时结果。我的代码首先使用未排序的非随机整数列表运行快速排序。然后它对先前的排序列表进行排序。使用我选择的枢轴,我预计快速排序在排序列表中运行比未排序列表最差。我已经用以下结果验证了这一点:

Quicksort 1st run (unsorted, non-randomized)
# of calls to exch(): 14
# of calls to sort(): 17
# of calls to partition():8
# of calls to less(): 47
Sorted?: true
Time to sort input: 0.004212 secs

Quicksort 2nd run (sorted)
# of calls to exch(): 25
# of calls to sort(): 40
# of calls to partition(): 19
# of calls to less(): 138
Sorted?: true
Time to sort input: 0.000535 secs

请注意,时间安排没有意义。Quicksort 2nd run 应该比 Quicksort 1st run 慢。

Timing code:
start();
Quick.sort(a);
stop();

private static void start(){
   start = System.nanoTime();       
}

private static void stop(){
   elapsed = (System.nanoTime() - start)/1E9;
}   

快速排序算法是正确的。所以我实现计时器的方式一定有问题。

完整代码:

public class Quick {

static int exchCount; //DEBUG
static int sortCount; //DEBUG
static int partitionCount; //DEBUG
static int compareCount; //DEBUG

public static void sort(Comparable[]a){
    //StdRandom.shuffle(a);
    exchCount=0; //DEBUG
    sortCount=0; //DEBUG
    partitionCount=0; //DEBUG
    compareCount=0; //DEBUG
    sort(a, 0, a.length-1);
    System.out.printf("# of calls to exch(): %d%n", exchCount); //DEBUG
    System.out.printf("# of calls to sort(): %d%n", sortCount); // DEBUG
    System.out.printf("# of calls to partition(): %d%n", partitionCount); // DEBUG
    System.out.printf("# of calls to less(): %d%n", compareCount); // DEBUG
    return;

}

private static void sort(Comparable a[], int lo, int hi){
    sortCount++; // DEBUG

    if (hi<=lo) return; // base case    
    int p = partition(a, lo, hi); // select partition
    sort(a, lo, p-1); // recursively sort left side of partition
    sort(a, p+1, hi); // recursively sort right side of partition

    return; 
}


private static int partition(Comparable[]a, int lo, int hi){    
    partitionCount++; //DEBUG
    int i = lo, j = hi+1; // set pointers i (left) & j (right)

    Comparable p = a[lo]; // select a partition point we'll use lo as default

    while (true){

        // continue walking right if values are < p
        // captures any value < p
        while (less(a[++i], p)) if(i==hi)break;

        // continue walking left if values are > p
        while (less(p, a[--j]));

        if(i>=j) break; // has i crossed j?

        exch(a, i, j);

    }

    exch(a, lo, j); 
    return j;
}


private static boolean less(Comparable a, Comparable b){
    compareCount++; //DEBUG
    return a.compareTo(b)<0;

}

private static void exch(Comparable[] a, int i, int j){
    exchCount++; //DEBUG
    Comparable tmp = a[i];
    a[i] = a[j];
    a[j] = tmp; 

}

}


public class SortClient {

static double start=0, elapsed=0;
public static void main(String[] args) {

    for(int i=0; i<10; i++){

        //Comparable[] a={"K","R","A","T","E","L","E","P","U","I"
        //  ,"M","Q","C","X","O","S"};
        //Comparable[] a = DataReader.readInt("http://algs4.cs.princeton.edu/14analysis/8Kints.txt");
        Comparable[] a={8,4,45,23,13,1,65,44,9,8,3,33,21};

        start();
        Quick.sort(a);
        stop();
        System.out.printf("Quicksort#1%n");
        System.out.printf("Sorted?: %b%n",isSorted(a));
        System.out.printf("Time to sort input: %f secs%n%n%n",elapsed);

        start();
        Quick.sort(a);
        stop();
        System.out.printf("Quicksort#2%n");
        System.out.printf("Sorted?: %b%n",isSorted(a));
        System.out.printf("Time to sort input: %f secs%n%n%n",elapsed);

    }
}

private static void start(){

    start = System.nanoTime();

}

private static void stop(){

    elapsed = (System.nanoTime() - start)/1E9;


}

private static boolean isSorted(Comparable[]a){

    for(int i=0; i<a.length-2; i++)
       if(a[i].compareTo(a[i+1])>0)
           return false;
    return true;

}

}

我不知道 Java 的 nanoTime() 调用有什么怪癖吗?有任何想法吗?

4

2 回答 2

2

“我们都知道,排序列表比未排序列表运行得更差”:这是一个大胆的说法。

Quicksort 的效率取决于对枢轴的正确选择:好的枢轴是这样的,它们以平衡的方式分割要排序的区域,从而使过程保持二分法,这会导致一种O(N.Lg(N))行为。相反,导致最大不平衡的错误选择会导致二次O(N²)退化,因为该过程仍然是增量的。

朴素的枢轴选择策略,例如“第一个元素”确实会导致排序序列出现最坏的情况。但是更明智的实施,例如“三的中位数(第一个、中间和最后一个)”将表现最佳。

于 2014-06-07T19:03:47.700 回答
0

正如@AbhisekBansal 指出的那样,快速排序在大型数组(即> 1000 个项目)上按预期运行。在对 4K 整数列表运行快速排序后,快速排序在所有迭代中都按预期执行(即 T*unsorted* < T*sorted*):

输出(前 4 次迭代):

Quicksort#1(unsorted)
calls to exch(): 11466
calls to sort(): 5329
calls to partition(): 2664
calls to less(): 60092
Sorted?: true
Time to sort input: 0.006784 secs

Quicksort#2(presorted)
calls to exch(): 3999
calls to sort(): 7999
calls to partition(): 3999
calls to less(): 8005998
Sorted?: true
Time to sort input: 0.079226 secs

Quicksort#1(unsorted)
calls to exch(): 11466
calls to sort(): 5329
calls to partition(): 2664
calls to less(): 60092
Sorted?: true
Time to sort input: 0.001649 secs

Quicksort#2(presorted)
calls to exch(): 3999
calls to sort(): 7999
calls to partition(): 3999
calls to less(): 8005998
Sorted?: true
Time to sort input: 0.079353 secs

Quicksort#1(unsorted)
calls to exch(): 11466
calls to sort(): 5329
calls to partition(): 2664
calls to less(): 60092
Sorted?: true
Time to sort input: 0.001680 secs

Quicksort#2(presorted)
calls to exch(): 3999
calls to sort(): 7999
calls to partition(): 3999
calls to less(): 8005998
Sorted?: true
Time to sort input: 0.079331 secs

Quicksort#1(unsorted)
calls to exch(): 11466
calls to sort(): 5329
calls to partition(): 2664
calls to less(): 60092
Sorted?: true
Time to sort input: 0.001625 secs

Quicksort#2(presorted)
calls to exch(): 3999
calls to sort(): 7999
calls to partition(): 3999
calls to less(): 8005998
Sorted?: true
Time to sort input: 0.079593 secs
于 2014-06-08T02:49:55.013 回答