Pourquoi mon algorithme de tri est-il plus rapide que celui de "Introduction to Algorithms" de H.Cormen?

Question

J'étudie ce livre depuis hier et après avoir compris et appliqué le premier algorithme, j'ai essayé d'aller seul et de regarder différemment. Voici, en Java, l'algorithme montré:

public static int[] sort(int[] array) 
{ 
    for(int i = 1; i < array.length; i++){ 
     int value = array[i]; 
     int j = i - 1; 

     while(j >= 0 && array[j] > value){ 
      array[j + 1] = array[j]; 
      j--; 
     } 
     array[j+1] = value; 
    } 

    return array; 
} 

Et voici le mien:

public static int[] sortb(int[] array) 
{ 
    for(int i = 0; i < array.length; i++){ 
     int value = array[i]; 
     int j = i; 

     while(j < array.length && value > array[j]){ 
      array[j] = array[j + 1]; 
      j++; 
     } 

     array[j] = value; 
    } 

    return array; 
} 

Pour 1 million d'appel de fonction pour chacun, je suis arrivé 32 ms pour le premier et 25 ms pour la deuxième . Je commence toujours avec des algorithmes, donc je n'ai aucune idée de la signification.

Answer 1

J'ai trouvé pourquoi votre tri est tellement plus rapide que l'original: Parce que vous ne faites rien du tout.

Dans votre code

int value = array[i]; 
    int j = i; 

    while(j < array.length && value > array[j]) { ... } 

Parce que j = i, donc value == array[j] avant d'entrer dans la boucle while, et donc votre corps de la boucle while ne sera jamais exécutée. Votre résultat de tri sera erroné. C'est la raison principale pour laquelle votre code est extrêmement rapide.

Answer 2

Dans mon expérience (lire expérience de l'étudiant) ce genre de différentes valeurs ont peu de signification. Peut-être que vous avez eu un processus d'arrière-plan qui a pris/libéré un peu plus de ressources de l'un à l'autre. Peut-être que le cas spécifique que vous avez essayé d'organiser était meilleur pour l'un des algorithmes que pour l'autre.

Peut-être, si vous avez utilisé différents tableaux au hasard, l'un d'entre eux était plus proche d'être triés que l'autre ..

Pour avoir de bonnes mesures, vous devez généralement faire beaucoup de tests, non seulement un. Par exemple, générer des tableaux de 1k 10k éléments chacun et chacun de trier ce tableau avec les deux algorythmes ..

Quoi qu'il en soit, parfois spécifiques caractéristiques d'une langue ou d'un compilateur peut générer des résultats différents pour algorythmes avec théoriquement la même complexité exacte (un exemple: une fois que j'ai remarqué en C++ si vous traversez un tableau bidimensionnel d'abord par des colonnes puis par des lignes, vous aurez une vitesse très différente que si vous le faites dans l'autre sens, mais je ne me souviens pas était plus rapide tbh).