1

さまざまな配列サイズでさまざまな並べ替え方法の合計経過時間を取得しようとしています。サイズ = 100、1000、10000、および 100000 の経過時間を取得できますが、1000000 を試すと、結果が得られずに実行され続けます (1000000 は大きすぎると思いますか?)。妥当な時間でコンパイルされる nanoTime を使用して経過時間を取得する方法はありますか? どんな助けでも素晴らしいでしょう！

私のプログラム:

import java.util.Random;

public class Sorting {

public static void printArray(int[] array) {
    System.out.print("The Array: ");
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

public static void exchange(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void selectionSort(int[] array) {
    for (int fill = 0; fill < array.length - 2; fill++) {
        int minPos = fill;
        for (int j = fill + 1; j < array.length; j++) {
            if (array[j] < array[minPos]) {
                minPos = j;
            }
        }
        exchange(array, fill, minPos);
    }
}

public static void bubbleSort(int[] array) {
    for(int last = array.length - 1; last > 0; last--){
        for(int i = 0; i < last; i ++){
            if(array[i + 1] < array[i]){
                exchange(array, i, i + 1);
            }
        }
    }
}


public static void main(String[] args) {
    int size = 1000000;
    Random rand = new Random();
    int[] arrayToSort = new int[size];
    for (int i = 0; i < size; i++) {
        arrayToSort[i] = rand.nextInt(size);
    }

    //printArray(arrayToSort);
    long startSelect = System.nanoTime();        
    selectionSort(arrayToSort);
    long estSelectTime = System.nanoTime() - startSelect;
    System.out.println("elapsed time after Selection sort for n = " + size + " : " + estSelectTime);
    //printArray(arrayToSort);
//        long startBubble = System.nanoTime();                
//        bubbleSort(arrayToSort);
//        long estBubTime = (System.nanoTime() - startBubble)/size;
//        System.out.println("elapsed time after Bubble sort for n = " + size + " : " + estBubTime);
    //printArray(arrayToSort);

}

}
4

2 に答える 2

0

私が実行する場合

 100K =>   4.7 secs
 200K =>  18.5 secs
 500K => 116.7 secos
1000K => 4 mins (estimated)

注：このように選択ソートを変更すると

public static void selectionSort(int[] array) {
    for (int fill = 0; fill < array.length - 2; fill++) {
        int minPos = fill;
        int minValue = array[minPos];
        for (int j = fill + 1; j < array.length; j++) {
            if (array[j] < minValue) {
                minPos = j;
                minValue = array[j];
            }
        }
        exchange(array, fill, minPos);
    }
}

200K は 18.5 秒ではなく 14.6 秒かかります。

于 2014-03-30T18:48:47.980 に答える