Quicksort ne fonctionne pas

Question

Ceci est tout mon code pour ma méthode quicksort, cela fonctionne sur un ensemble de 21 nombres, mais pas sur mon jeu de données réel, qui est d'environ 100000. Je n'ai aucune idée de ce qui ne va pas, j'ai été bidouillant pendant deux heures et il est dû 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

Assomption:

• a détient 10'000 échantillons,
• départ est de 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)); 
  

fin/4 est 250

.. vous échangez des valeurs en dehors de votre sous-ensemble de tri.

Answer 2

Cela ne ressemble pas à un problème de devoirs. Si c'était un problème de devoirs, l'auteur aurait écrit environ sept à dix lignes de code, avec une preuve d'efficacité, et l'a fait entrer. Ce type essaie d'être chic, et ça le mord dans le derrière. Vous pouvez dire par la façon dont il tombe à insertion-tri pour les soi-disant "petits" intervalles. (Indice: la taille de l'intervalle de seuil est plus de la moitié de la taille des données de test .. Donnez à votre algorithme une certaine marge de recurse si vous voulez bien le tester.) Deuxièmement, il fait un travail supplémentaire pour trouver un pivot idéal. Ce genre de complexité a un coût.

Ceci est un amateur au travail. Ce dont il a besoin n'est pas seulement une réponse. Il a besoin d'une approche pour résoudre les problèmes difficiles. Quicksort est juste le véhicule de cette éducation.

Voici mon approche.

L'astuce consiste à écrire Quicksort en tant que Quicksort, à le faire fonctionner, puis à s'inquiéter des astuces spéciales. Tuez le bruit à propos de l'insertion en triant les petits intervalles. Supposons simplement que tout intervalle de taille zéro ou un est déjà trié (ce qui est votre cas de base) et travaillons à faire fonctionner votre code de partitionnement en utilisant l'extrémité gauche de l'intervalle comme pivot (comme dans le Quicksort original classique). Envisagez d'imprimer les résultats de vos données après un passage de partition afin de vous montrer que cela fonctionne. Vous allez développer 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 séparer la sélection du pivot dans une fonction et jouer avec l'implémentation.

Bonne chance, et appréciez votre projet. Ne pas oublier, cependant: Nous voulons des minutages, et surtout des comparaisons de temps avec la routine de tri dans la bibliothèque standard!