私のバブルソートアルゴリズムは、私のプログラムの選択と挿入のソートアルゴリズムより速いのはなぜですか？

Question

私のバブルソートアルゴリズムは、私の選択と挿入ソートアルゴリズムよりも私のプログラムで高速ですか？

このプログラムは、グリッドを含むプログラムで、グリッドには、ソートする必要がある異なる番号の番号が含まれています。行には、ソートアルゴリズムが異なり、クリックされた数値のソートに使用されますグリッド内では、アルゴリズムがランダムに生成された＃をソートするのに要した時間がプリントアウトされます。

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
int n = 99; 
int min, tmp, i, j, min_id, data, k, temp; 
int[] array = new int [n]; 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void setup() { 

    size(661, 500); 
    background(255); 

    initArr(); 
    bubbleSort(); 
    selectionSort(array, n); 
    insertionSort(array); 
    quickSort(0, n - 1); 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void draw() { 

    drawGrid(); 
    labels(); 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void initArr() { 

    for (i = 0; i < n; i ++) { 
    array[i] = (int)random(1, 10); 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void mouseReleased() { 
    for (int j = 1; j < 5; j ++) { 

    for (int i = 1; i < 6; i ++) { 

     if (mouseX > i * 110 && mouseX < i * 110 + 110 && mouseY > j * 80 && mouseY < j * 80 + 80) { 
     println("X:" + " " + i + " " + "Y:" + " " + j); 

     if (i == 1 && j == 1) { 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 1) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 1) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 1) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 1) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 1 && j == 2) { 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 2) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 2) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 2) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 2) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 1 && j == 3) { 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 3) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 3) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 3) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 3) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 1 && j == 4) { 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 4) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 4) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 4) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 4) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } 
     } 
    } 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void labels() { 

    for (k = 0; k < 5; k ++) { 
    rect(0, k * 80, 110, 80); 
    rect(k * 110 + 110, 0, 110, 80); 
    } 

    for (k = 0; k < 3; k ++) { 
    rect(k * 183.5 + 110, 400, 183.5, 80); 
    } 

    fill(0); 
    text("ALGORITHM", 20, 45); 
    text("BUBBLE", 20, 125); 
    text("SELECTION", 20, 205); 
    text("INSERTION", 20, 285); 
    text("QUICK", 20, 365); 

    text("100", 150, 45); 
    text("1000", 260, 45); 
    text("10000", 365, 45); 
    text("100000", 470, 45); 
    text("1000000", 575, 45); 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void drawGrid() { 

    //----Grid---- 
    for (j = 1; j < 5; j ++) { //columns 
    for (i = 1; i < 6; i ++) { // rows 

     fill(255); 
     if (i != 0 && j != 0 && j <= 4 && i <= 5) { 
     if (mouseX > i * 110 && mouseX < i * 110 + 110 && mouseY > j * 80 && mouseY < j * 80 + 80) 
      fill(255, 200, 200); 
     } else 
     fill(255); 

     rect(i * 110, j * 80, 110, 80); 
    } 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void bubbleSort() { 

    for (i = 0; i < n - 1; i++) { 
    for (j = 0; j < n - i - 1; j++) 
     if (array[j] > array[j+1]) { 
     temp = array[j]; 
     array[j] = array[j + 1]; 
     array[j + 1] = temp; 
     } 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void selectionSort (int array[], int n) { 

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

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void insertionSort(int[] array) { 

    for (int i = 1; i < array.length; i++) 
    { 
    // a temporary copy of the current element 
    temp = array[i]; 

    // find the position for insertion 
    for (j = i; j > 0; j--) 
    { 
     if (array[j - 1] < temp) 
     break; 
     // shift the sorted part to right 
     array[j] = array[j - 1]; 
    } 

    // insert the current element 
    array[j] = temp; 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void quickSort(int low, int high) { 
    i = low; 
    j = high; 
    // calculate pivot number, I am taking pivot as middle index number 
    int pivot = array[low+(high-low)/2]; // Divide into two arrays 
    while (i <= j) { 
    /** 
    * In each iteration, we will identify a number from left side which 
    * is greater then the pivot value, and also we will identify a number 
    * from right side which is less then the pivot value. Once the search 
    * is done, then we exchange both numbers. 
    */ 
    while (array[i] < pivot) { 
     i++; 
    } 
    while (array[j] > pivot) { 
     j--; 
    } 
    if (i <= j) { 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     //move index to next position on both sides 
     i++; 
     j--; 
    } 
    } 
    // call quickSort() method recursively 
    if (low < j) 
    quickSort(low, j); 
    if (i < high) 
    quickSort(i, high); 
} 

Answer 1

あなたはいくつかのことを逃した：

1. Java用のベンチマークを書くことにより、とりわけJVM自体が非常に多くを行うソフトウェアのかなり複雑な部分であるという事実にan art on its ownです
2. クイックソートがasymptotically better runtime（math-addendaはthis answerを参照）という事実は、あるブレーク・ポイントが存在することを意味し、その後は高速化されます。より小さな入力に対しては、漸近的に悪いアルゴリズムが実際にはより良い選択であるかもしれない。
3. マイクロ秒単位で時間を測定しますが、これはあなたのものと同じくらい小さな入力では分解能が低すぎます。測定された時間はランダムノイズよりもはるかに大きくはない
4. ソート関数に渡される入力の状態。あなたの入力は多かれ少なかれランダムかもしれませんが、すべての値は1から10までの範囲にあります。ランタイムの実装を実際にテストする場合は、より広い範囲の値を入力し、すべての関数が同じ入力。ほとんどのソートアルゴリズムは、特定の条件に一致する入力が与えられた場合、特別な方法で動作します。例えば。正しく実装されたバソポートはソートされた配列のO(n)で実行されます。
5. 最後に重要なのは、入力サイズがベンチマークを有意義にするには小さすぎることです。実装のタイミングにおける最も重要な要素は、パフォーマンスではなくスレッドスケジューリング（およびOSによって導入される他のノイズ）です。あなたがそれらを比較したいならば、あなたのアルゴリズムを真剣に働かせてください。