Pourquoi mon algorithme de tri à bulles est-il plus rapide que mes algorithmes de sélection et d'insertion dans mon programme?

Question

Pourquoi mon algorithme de tri à bulles est-il plus rapide que mes algorithmes de sélection et d'insertion dans mon programme? Ce programme est un programme qui contient une grille et dans la grille, les colonnes contiennent un nombre différent de nombres qui doivent être triés, et les lignes ont des algorithmes de tri différents, qui sont utilisés pour trier le nombre de chiffres cliqués dans la grille, le temps nécessaire à l'algorithme pour trier les # générés aléatoirement est imprimé.

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
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

Vous avez manqué quelques petites choses sur:

1. repères d'écriture pour Java est an art on its own en raison du fait que, entre autres choses la machine virtuelle Java lui-même est un morceau assez complexe de logiciel qui fait beaucoup de optimisation avec votre code, le recompile, etc.
2. Le fait que quicksort a un asymptotically better runtime (voir l'addenda mathématique de this answer) signifie qu'il y aura un certain seuil de rentabilité après lequel il sera plus rapide. Pour les plus petites entrées un algorithme asymptotiquement pire pourrait effectivement être le meilleur choix.
3. Vous mesurez le temps en micro-secondes, ce qui est une résolution trop faible pour des entrées aussi petites que les vôtres. Le temps mesuré ne sera pas beaucoup plus que le bruit aléatoire
4. L'état de l'entrée transmise aux fonctions de tri. Votre entrée peut être plus ou moins aléatoire, mais toutes les valeurs se situent entre 1 et 10. Si vous voulez vraiment tester vos implémentations pour leur exécution, donnez-leur une entrée avec une plus grande plage de valeurs et assurez-vous que toutes les fonctions reçoivent la même contribution. La plupart des algorithmes de tri se comportent d'une manière spéciale, s'ils sont alimentés par des entrées qui correspondent à certains critères. Par exemple. un bubbleort correctement implémenté doit s'exécuter en O(n) sur un tableau trié.
5. Dernier point, mais non des moindres: la taille d'entrée est trop petite pour que le benchmark soit significatif. Le facteur le plus important dans le timing de votre implémentation est la planification de threads (et d'autres bruits introduits par le système d'exploitation), et non les performances. Laissez vos algorithmes travailler sérieusement, si vous voulez les comparer.