Modification de quickSort avec insertionSort

Question

J'ai donc dû créer un algorithme quicksort en utilisant pivot comme élément central du tableau. Je l'ai fait tout bien. Mais maintenant il me demande de modifier l'algorithme quickSort de sorte que lorsque l'une des sous-listes se réduit à moins de 20, alors je trier la sous-liste en utilisant un insertionSort.

Je semblais l'avoir fonctionné. Il compile et trie le tableau parfaitement, mais je ne suis pas sûr si je l'ai fait juste parce que la différence de temps de processeur entre le quicksort modifié et le quicksort normal n'est pas différent. Mon incertitude est dans la méthode récursive recQuickSortC où j'ai les instructions "> = 20". Je ne suis pas sûr que ce soit la bonne façon d'implémenter la modifcation, ça pourrait être complètement faux, tout ce que je sais, c'est qu'elle le trie correctement. Toute aide serait bien, merci.

Voici mon algorithme de tri rapide modifié:

public void quickSortC(T[] list, int length) 
{ 
    recQuickSortC(list, 0, length - 1); 
}//end quickSort 

private void recQuickSortC(T[] list, int first, int last) 
{ 
    if (first < last) 
    { 
     int pivotLocation = partitionA(list, first, last); 
     if ((pivotLocation - 1) >= 20) 
      recQuickSortC(list, first, pivotLocation - 1); 
     else 
      insertionSort(list,pivotLocation -1); 

     if ((pivotLocation - 1) >= 20) 
      recQuickSortC(list, pivotLocation + 1, last); 
     else 
      insertionSort(list, pivotLocation + 1); 
    } 
}//end recQuickSort 

private int partitionA(T[] list, int first, int last) 
{ 
    T pivot; 

    int smallIndex; 

    swap(list, first, (first + last)/2); 

    pivot = list[first]; 
    smallIndex = first; 

    for (int index = first + 1; index <= last; index++) 
    { 
     if (list[index].compareTo(pivot) < 0) 
     { 
      smallIndex++; 
      swap(list, smallIndex, index); 
     } 
    } 

    swap(list, first, smallIndex); 

    return smallIndex; 
}//end partition 


    public void insertionSort(T[] list, int length) 
{ 
    for (int unsortedIndex = 1; unsortedIndex < length; 
           unsortedIndex++) 
    { 
     Comparable<T> compElem = 
        (Comparable<T>) list[unsortedIndex]; 

     if (compElem.compareTo(list[unsortedIndex - 1]) < 0) 
     { 
      T temp = list[unsortedIndex]; 

      int location = unsortedIndex; 

      do 
      { 
       list[location] = list[location - 1]; 
       location--; 
      } 
      while (location > 0 && 
        temp.compareTo(list[location - 1]) < 0); 

      list[location] = (T) temp; 
     } 
    } 
}//end insertionSort 

Si vous avez remarqué Theres un tas de A, B et C du côté des méthodes becuase je dois faire beaucoup de différents algorithmes de tri rapide. Je mets tout le code qui est utilisé dans l'algorithme. Faites-moi savoir si vous en avez besoin plus merci.

Answer 1

Cela me semble parfaitement bien, même si au lieu de tester si la distance de pivotement est d'au plus 20, je voudrais simplement réécrire la méthode quicksort pour dire if (last - first <= 20) { do insertion sort} else { do normal quicksort}. De cette façon, vous n'avez qu'à écrire le chèque une fois, par opposition à une fois pour chaque "côté" de la récursivité. Cela dit, il est probable que votre benchmark ne vous donne pas de bonnes estimations de temps - c'est-à-dire que votre code est probablement plus rapide que vous ne le pensez - simplement parce que l'obtention de benchmarks précis en Java n'est pas triviale. évident.