なぜ3つのアルゴリズムの平均時間が負であるのですか？

Question

私はステップサイズ10000の10000から50000の範囲のサイズの配列を使用しなければならず、3つのアルゴリズムすべてに同じ入力を与え、各入力に対して実行を100回繰り返し、実行をナノ秒単位で測定します （System.nanoTime ））、平均時間をミリ秒単位で報告します。 これは私が下で行ったことですが、平均のうちのいくつかは否定的です。私はなぜそれを知らないのですか？

import java.util.Arrays; 

public class Sort{ 

    public static void main(String[]args){ 

     double[] arr5 = new double[50000]; 

     for(int i=0;i<arr5.length;i++) 
     arr5[i] = Math.random(); 

     selectionSort(arr5,10000); 
     bubbleSort(arr5,10000); 
     quickSort(arr5,10000); 

     selectionSort(arr5,20000); 
     bubbleSort(arr5,20000); 
     quickSort(arr5,20000); 

     selectionSort(arr5,30000); 
     bubbleSort(arr5,30000); 
     quickSort(arr5,30000); 

     selectionSort(arr5,40000); 
     bubbleSort(arr5,40000); 
     quickSort(arr5,40000); 

     selectionSort(arr5,50000); 
     bubbleSort(arr5,50000); 
     quickSort(arr5,50000); 
    } 

    public static void selectionSort(double [] A,int n){ 
     int sum = 0; 
     System.out.println("Algorithm 1"); 
     for(int s=0;s<100;s++){ 
     long arr[] = new long[100]; 

     long startTime = System.nanoTime(); 

     for(int i=0;i<n-1;i++){ 
      int min = i; 
      for(int j=i+1;j<n;j++){ 
       if(A[j] < A[min]) 
        min=j;} 
      double tmp = A[i]; 
      A[i] = A[min]; 
      A[min]=tmp;} 

     long endTime = System.nanoTime(); 

     arr[s] = endTime - startTime; 
     //System.out.println(arr[s]); 
     sum+=arr[s]; 
     } 
     System.out.println("Average:" + ((sum/100)*Math.pow(10,-6))); 

    } 

    public static void bubbleSort(double A [],int n){ 
     int sum = 0; 
     System.out.println("\nAlgorithm 2"); 
     for(int s=0;s<100;s++){ 
     long[] arr = new long[100]; 

     long startTime = System.nanoTime(); 

     for(int i=0;i<n-1;i++){ 
      for(int j=0;j<n-1-i;j++){ 
       if(A[j]<A[j+1]){ 
        double tmp = A[j]; 
        A[j] = A[j+1]; 
        A[j+1] = tmp;}}} 

     long endTime = System.nanoTime(); 

     arr[s] = endTime - startTime; 
     //System.out.println(arr[s]); 
     sum+=arr[s]; 
     } 
     System.out.println("Average:" + ((sum/100)*Math.pow(10,-6))); 

    } 

//algorithm 3 
    public static void quickSort(double A [],int n){ 
     int sum = 0; 
     System.out.println("\nAlgorithm 3"); 
     long[] arr = new long[100]; 

     for(int i=0;i<100;i++){ 
     long startTime = System.nanoTime(); 

     Arrays.sort(A,0,n-1); 

     long endTime = System.nanoTime(); 

     arr[i] = endTime - startTime; 
     //System.out.println(arr[i]); 
     sum+=arr[i]; 
     } 
     System.out.println("Average:" + ((sum/100)*Math.pow(10,-6))); 

    } 

} 

Answer 1

あなたの計算に使用する変数sumはタイプintです。 sumを増やすと、endTime - startTimeの結果がかなり大きい値になってオーバーフローします。 sumのオーバーフローが発生すると、その値は最小値（負の値）に戻り、再び増加し続けます。

修正：sumのタイプをlongに変更してください。彼らは計算に使用されていないと、各ループでリセットされているようarr呼ば

別コメント

あなたの配列が冗長に見えます。

たとえば、bubbleSort()の方法です。配列long[] arr = new long[100];を宣言して、forループ内に初期化します（for(int s=0;s<100;s++)）。

今現在ではこの配列arrの唯一の目的は、次いで、sum（sum+=arr[s];）を増加させるために使用されるインデックスs、でendTime - startTimeの結果を格納することです。

これが唯一の目的ならば、sum += endTime - startTimeを実行してアレイを完全に削除しないでください。あなたがInfactはこの配列内のすべての結果を追跡するつもりなかった場合

、あなたは、現在、それは再宣言し、各反復で初期化され、forループfor(int s=0;s<100;s++)のlong[] arr = new long[100];外を移動する必要があります。出力された

for (int i = 0; i < 5; i++) { 
    int[] arr = new int[5]; 
    arr[i] = (i + 1); 
    System.out.println(Arrays.toString(arr)); 
} 

：

[1, 0, 0, 0, 0] 
[0, 2, 0, 0, 0] 
[0, 0, 3, 0, 0] 
[0, 0, 0, 4, 0] 
[0, 0, 0, 0, 5] 

配列が前のループに宣言されている場合は、bubbleSort()でやって他の方法をされているものを複製し、この小さな例を考えてみ実証するために

、その行動はより意味をなさないはずである。

この場合、出力は次のようになります。

[1, 0, 0, 0, 0] 
[1, 2, 0, 0, 0] 
[1, 2, 3, 0, 0] 
[1, 2, 3, 4, 0] 
[1, 2, 3, 4, 5] 

はforループでコンソールにあなたの配列arrの内容を印刷し、あなたは私が何を意味するかわかります。