Quicksort ne fonctionne pas

Question

Ceci est tout mon code pour ma méthode de tri rapide, il fonctionne sur un ensemble de 21 numéros, mais pas sur mon vrai jeu de données, qui est d'environ 100000. Je ne sais pas ce qui ne va pas, je suis tripotage pour deux heures et il est pour bientôt! Toute aide serait la bienvenue

public static void hybridQuicksort( int[] a, int start, int end )
{
    final int MIN = 13;
    if ( end - start >= MIN )
    {
        int pivot = findPivot( a, start, end );
        pivot = partition ( a, start, end, pivot );
        hybridQuicksort( a, start, pivot - 1 );
        hybridQuicksort( a, pivot + 1, end);
    }
    else
    {
        insertionSort( a, start, end );
    }
}

//partitions the array based on the pivot
public static int partition( int[] a, int start, int end, int pivot )
{
    int up = start + 1;
    int down = end;

    while ( up <= down )
    {

        while ( a[up] <= pivot)
            up++;

        while ( a[down] > pivot)
            down--;

        if ( up <= down )
            swap( a, up, down );
    }

    swap( a, start, down );

    return up;
}

//finds the first, middle, middle of first and middle, middle of middle and last
//and last numbers and sets their median as the pivot
public static int findPivot( int[] a, int start, int end )
{
    //swap the 4 numbers to the start of the array, leaving the first as is
    swap( a, start + 1, end - 1 );
    swap( a, start + 2, (start + end) / 2);
    swap( a, start + 3, end / 4);
    swap( a, start + 4, (end / 2) + (end / 4) );

    //sort the 5 numbers
    insertionSort( a, 0, 5 );

    //swap the median to the front, that's the pivot
    swap( a, start, start + 2 );
    //return the pivot
    return a[start];
}

Answer 1

Hypothèse:

• a détient 10'000 échantillons,
• start 500

• fin est 1000

  //swap the 4 numbers to the start of the array, leaving the first as is
  swap( a, start + 1, end - 1 );
  swap( a, start + 2, end / 2);
  swap( a, start + 3, end / 4);
  swap( a, start + 4, (end / 2) + (end / 4) );
  

end / 4 est 250

.. vous échangez des valeurs de l'extérieur de votre tri-sous-ensemble .

Answer 2

Cela ne ressemble pas à un problème de travail. Était-ce un problème de travail, l'auteur aurait écrit sur sept à dix lignes de code, avec une preuve d'efficacité, et l'a transformé. Ce mec essaie d'être de fantaisie, et il lui mordre dans le dos. Vous pouvez dire par la façon dont il tombe à insertion-tri pour les soi-disant intervalles « petits ». (Indice: la taille de l'intervalle de seuil est plus de la moitié de la taille des données de test Donnez votre algorithme de la place à récursif si vous voulez tester bien..) En second lieu, il y a le travail supplémentaire qu'il fait pour trouver un pivot idéal. Ce genre de complexité a un coût.

Ceci est un amateur au travail. Ce qu'il a besoin est non seulement une réponse. Il a besoin d'une approche pour résoudre des problèmes difficiles. Quicksort est juste le véhicule pour que l'éducation.

Voici mon approche.

L'astuce consiste à écrire Quicksort comme Quicksort, le faire fonctionner, puis vous soucier de fantaisie trucs spéciaux. Tuer le bruit sur l'insertion de petits intervalles de tri. Il suffit de supposer que tout intervalle de taille zéro ou un est déjà trié (qui est votre cas de base), puis travailler à rendre votre travail de code de partitionnement en utilisant l'extrémité gauche de l'intervalle comme le pivot (comme dans Quicksort d'origine classique), et vous pouvez envisager d'imprimer les résultats de vos données après un passage de partitionnement comme une façon de vous montrer que cela fonctionne. Vous développerez des compétences de test de cette façon. Quoi qu'il en soit, une fois que vous avez un quicksort de travail, alors vous pouvez faire des choses comme la sélection de pivot séparé en fonction et jouer avec la mise en œuvre.

Bonne chance et profiter de votre projet. Ne pas oublier, si: Nous voulons timings, et surtout des comparaisons de temps avec la routine de tri dans la bibliothèque standard