Quicksort/Insertion Trier le combo plus lentement que Quicksort?

Question

Je cours Quicksort 10 fois et j'obtiens le temps moyen moyen. Je fais la même chose pour la combinaison de tri Qicksort/Insertion, et il semble être plus lent que le simple tri rapide.

est ici la partie du code où j'appelle InsertionSort

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) { 
     int indexofpartition; 
     if(max - min > 0) { 
      if((max - min) <= 10) { 
       // Use InsertionSort now 
       InsertionSort.sort(data); 
       return; 
      } else { 
       indexofpartition = findPartition(data, min, max); 

       OptQSort2(data, min, indexofpartition - 1); 

       OptQSort2(data, indexofpartition + 1, max); 
      } 
     } 

} 

Et la Quicksort régulière est la même chose que l'extrait ci-dessus, mais sans la condition if qui appelle InsertionSort.

FindPartition est la suivante:

public static <T extends Comparable<? super T>> int findPartition(T[] data, int min, int max) { 
    int left, right; 
    T temp, partitionelement; 
    int middle = (min + max)/2; 

    partitionelement = data[middle]; 
    left = min; 
    right = max; 

    while(left < right) { 
     while(data[left].compareTo(partitionelement) <= 0 && left < right) 
      left++; 

     while(data[right].compareTo(partitionelement) > 0) 
      right--; 

     if(left < right) { 
      temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
     } 
    } 

Le temps moyen pour seulement Quicksort et OptSort2 (qui utilise le tri par insertion) sont

Sorted using QuickSort in: 3858841 
Sorted using OptQSort2 in: 34359610 

Toutes les idées pourquoi? La taille de la séquence est-elle importante? J'utilise un tableau Integer [] de 1000 éléments pour cela

Answer 1

En OptQSort2, pour les petites partitions, vous avez l'appel de fonction suivante:

InsertionSort.sort(data); 

Est-ce supposé insertion trier la petite partition? Il semble que vous soyez en train de trier le tableau entier. Ne devriez-vous pas passer les index min et max à InsertionSort?

Une autre option consiste simplement à ne pas travailler sur les petites partitions pendant OptQSort2. Ensuite, effectuez un seul passage InsertionSort sur l'ensemble du tableau après OptQSort2 a fait son travail.

Answer 2

Vous aurez besoin d'un tableau d'entiers beaucoup plus grand pour que le test soit pertinent. À ce stade, tester probablement la condition if ralentit votre algorithme dans le cas QS + IS.

Testez un grand nombre de chiffres et passez à l'état IS lorsque la taille des données est suffisante pour tenir dans le cache L1, c'est-à-dire 32 à 64 ko.

Answer 3

Le premier suspect est évidemment votre méthode de tri par insertion. Est-ce que ça trie vraiment par exemple?

Vous devrez également le tester plus de 10 fois pour réchauffer la JVM. Et aussi pour les tester dans les deux ordres afin de ne pas bénéficier de l'échauffement effectué par l'autre. Je suggérerais 100 ou 1000 tests. Et ils doivent tous être sur le même jeu de données aussi.

Answer 4

Vous ne devez pas appeler InsertionSort chaque fois que vous avez un sous-tableau d'au plus 10 éléments. Ne faites rien:

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) { 
    int indexofpartition; 
     if((max - min) > 10) { 
      indexofpartition = findPartition(data, min, max); 

      OptQSort2(data, min, indexofpartition - 1); 

      OptQSort2(data, indexofpartition + 1, max); 
     } 

} 

Lorsque vous appel terminé InsertionSort pour tout le tableau.