2

配列のサイズを毎回 100 ずつインクリメントして、クイックソートでランタイム分析を実行する必要があります。ただし、System.nanoTime を使用してランタイムを測定すると、結果は期待どおりになりません (私のグラフは O(2^n) のように見えます)。配列が約 800 に達するたびに、時間が急上昇します。コードのどこが間違っているのか誰か教えてください。

また、配列サイズごとに1回だけクイックソートを実行したいので、カウント部分は現時点では無関係です。

import java.util.Random;


public class Quickworking {

public static void main(String[] args) {
    Random rand = new Random();
    int count2;
    long total = 0;
    count2 = 1;
    int [] myArray = new int[1400];   

                //generates random array
    for (int i = 0; i < myArray.length; i++){
        myArray[i] = rand.nextInt(100) + 1;
        //System.out.print(myArray[i] + ", ");
    }

            //loop sort n amount of times
    for (int count = 0; count < count2; count++){

            //calls the sort method on myArray giving the arguments
        long start = System.nanoTime();
        sort( myArray, 0, myArray.length - 1 );
        long end = System.nanoTime();
        System.out.println(end - start );
        total += (end - start);
    }
    //long average = (long) total / (long) count2;

    //System.out.println(average);


    //prints the sorted array
    //for (int i = 0; i <myArray.length; i++){
    //  System.out.print(myArray[i] + ", ");
    //}

}

public static int sort(int myArray[], int left, int right){
    int i = left, j = right;
    int temp;
    int pivot = myArray[(left + right) / 2];
    //System.out.println("here are the pivot numbers " + pivot + ", ");


    if (i <= j){

        while (myArray[i] < pivot) //&& (i<right))  
            i++;
        while (myArray[j] > pivot) //&& (j>left))  
            j--;
        if (i <= j){
            temp = myArray[i];
            myArray[i] = myArray[j];
            myArray[j] = temp;
            i++;
            j--;


        }
    } 

    if (left < j) sort(myArray, left, j);
    if (i < right) sort(myArray, i, right);

    return i;

}
}
4

2 に答える 2

2

既にソートされた配列をソートするときのクイックソートの動作は O(n^2) です。配列がコードで初めてソートされた後、ソートされた配列をソートします。これにより、クイックソートの最悪のケースが得られます。これを実際にテストするには、毎回完全に新しいランダム配列を生成する必要があります。

于 2012-12-08T16:18:37.917 に答える
1

QuickSort は、既に並べ替えられたデータではうまく機能しません。こちらをご覧ください: http://en.wikipedia.org/wiki/Quicksort

より正確な結果を得るには、for ループ内で配列をランダム化する必要があります。

于 2012-12-08T16:22:47.923 に答える