L'algorithme quicksort C# ne marche pas

Question

Je viens de travailler sur l'implémentation de quicksort en C# mais j'ai fait face à un tel problème. Quand je me sers ma fonction

static void QS(int[] arr, int left, int right){ 
     int pivot = left; 
     int temp; 
     int i = left + 1; 
     int j = left + 1; 

     do {  
     if (arr [i] < arr [pivot]) { 
       temp = arr [j]; 
       arr [j] = arr [i]; 
       arr [i] = temp; 
       i++; 
      } 
      else{} 
     j++; 
     }while(j<=right); 

      temp = arr [pivot]; 
      arr [pivot] = arr [i - 1]; 
      arr [i - 1] = temp; 
} 

Pour un tableau

int[] arr = { 12, 9, 19, 8, 7, 13, 10, 71, 18, 34, 90, 15, 3 }; 

Je reçois les résultats comme ceci: 9, 12, 19, 8, 7, 13, 10, 71, 18, 34, 90, 15, 3. Des heures ont été consacrées à ce que je n'arrive toujours pas à comprendre Pourquoi index je ne procède pas. Peut-être qu'il y a plus de problèmes que je ne le pense. J'ai omis les appels récursifs pour se concentrer sur la fonction elle-même. J'utilise ce pseudo-code:

Partiton(A,l,r) 
//[input corresponds to A[l…r]] 
p:=A[l] 
i:=l+1 
    for 
    j=l+1 to r 
    if A[j] < p 
    swap A[j] and A[i] 
    i:=i+1 
swap A[l] and A[i‐1] 

Answer 1

Plusieurs choses:

Youre manquant les comparaisons (en boucle) dans le do while qui se déplacent les pointeurs d'index, et les appels récursifs qui font quicksort fonctionnent réellement . Rappelez-vous quand vous échangez vos valeurs, incrémentez i et décrémentez j. Deuxièmement, pour les valeurs i et j, ne pas ajouter 1 à ces index car ils pourraient vous donner des erreurs hors limites, je suppose que vous appelerez quicksort comme suit: quicksort (arr, 0, arr.Length - 1) ;. Enfin, veuillez choisir votre pivot en tant que valeur médiane, car cela donne des temps et des résultats de tri beaucoup plus rapides, plutôt que de choisir la première valeur dans le tableau.

Voici comment j'écrire ceci:

quicksort(arr[], begin, end) 
    { 
     pivot = (begin + end)/2 
     left = begin; 
     right = end; 
    while (left <= right) 
    { 
     while (arr[left] < pivot) 
     { 
      left++; 
     } 
     while (arr[right] > pivot) 
     { 
      right--; 
     } 
     if (left <= right) 
     { 
      swap(arr, left, right); 
      left++; 
      right--; 
     } 
    } 
    //do your recursive call logic here 
}