Le tri rapide ne triage pas correctement

Question

En essayant d'apprendre à faire une implémentation de Quicksort, je ne peux pas savoir pourquoi le tri n'est pas correct.

En utilisant cette séquence:

6, 7, 12, 5, 9, 8, 65, 3

Il renvoie ceci:

3, 5, 7, 8, 9, 65 , 12, 6

Il semble trier un peu, mais pas tous. Qu'ai-je manqué?

Voici mon code:

static void Main(string[] args) 
     { 
      QuickSort qs = new QuickSort(); 

      int[] arr = new int[] { 6, 7, 12, 5, 9, 8, 65, 3 }; 

      foreach (int l in arr) 
      { 
       Console.Write(l + ", "); 
      } 

      int left = 0; 
      int right = arr.Count() - 1; 

      int[] arrr = qs.DoQuickSort(ref arr, left, right); 
      Console.WriteLine("Sorted List: "); 
      foreach (int i in arrr) 
      { 
       Console.Write(i + " "); 
      } 



      Console.ReadLine(); 
     } 

    public int Partition(int[] array, int left, int right, int PivotIndex) 
    { 
    int pivValue = array[PivotIndex]; 

    array = Swap(ref array, PivotIndex, right); 

    int storeIndex = left; 

    for (int i = PivotIndex; i < right-1; i++) 
    { 
     if (array[i] <= pivValue) 
     { 
      array = Swap(ref array, i, storeIndex); 
      storeIndex = storeIndex + 1; 
     } 
    } 

    array = Swap(ref array, storeIndex, right); 

    return storeIndex; 
} 

public int[] Swap(ref int[] arr, int first, int second) 
{ 
    int temp = arr[first]; 
    arr[first] = arr[second]; 
    arr[second] = temp; 

    return arr; 
} 

public int[] DoQuickSort(ref int[] array, int left, int right) 
{ 
    if (right > left) 
    { 
     int PivIndex = (left + right)/2; 
     int newPivIndex = Partition(array, left, right, PivIndex); 
     DoQuickSort(ref array, left, newPivIndex - 1); 
     DoQuickSort(ref array, newPivIndex + 1, right); 
    } 

    return array; 
} 

Answer 1

En plus de mon commentaire sur la question elle-même, je voulais souligner que les Swap() et DoQuickSort() méthodes ne ont pas besoin de retourner le tableau (selon ma note dans le commentaire qui explique que le tableau est lui-même une référence). À cette fin, votre code pour faire le travail devrait ressembler à ce qui suit:

public int Partition(int[] array, int left, int right, int pivotIndex) 
{ 
    int pivValue = array[pivotIndex]; 

    Swap(array, pivotIndex, right); 

    int storeIndex = left; 

    for (int i = left; i < right; i++) 
    { 
     if (array[i] <= pivValue) 
     { 
      Swap(array, i, storeIndex); 
      storeIndex = storeIndex + 1; 
     } 
    } 

    Swap(array, storeIndex, right); 

    return storeIndex; 
} 

public void Swap(int[] arr, int first, int second) 
{ 
    int temp = arr[first]; 
    arr[first] = arr[second]; 
    arr[second] = temp; 
} 

public void DoQuickSort(int[] array, int left, int right) 
{ 
    if (right > left) 
    { 
     int pivIndex = (left + right)/2; 
     int newPivIndex = Partition(array, left, right, pivIndex); 
     DoQuickSort(array, left, newPivIndex - 1); 
     DoQuickSort(array, newPivIndex + 1, right); 
    } 
} 

Answer 2

Dans votre méthode Partition vous avez une plage de boucle mal:

for (int i = PivotIndex; i < right-1; i++) 

deviendrais:

for (int i = left; i < right; i++) 

Commander le related wikipedia article qui dit:

function partition(array, left, right, pivotIndex) 
    pivotValue := array[pivotIndex] 
    swap array[pivotIndex] and array[right] // Move pivot to end 
    storeIndex := left 
    for i from left to right - 1 // left ≤ i < right 
     if array[i] ≤ pivotValue 
      swap array[i] and array[storeIndex] 
      storeIndex := storeIndex + 1 
    swap array[storeIndex] and array[right] // Move pivot to its final place 
    return storeIndex 

Avis: left ≤ i < right

Answer 3

Demandez-vous à remettre un poisson, ou à enseigner comment pêcher? Apprendre à déboguer vos propres programmes, plutôt que de compter sur d'autres personnes pour le faire pour vous, est une compétence qui vous sera très utile à l'avenir.

face à ce problème, la première chose que je voudrais faire est de marquer le code avec commentaires indiquant le sémantique fin de chaque section de code:

// Choose a pivot halfway along the portion of the list I am searching. 
int PivIndex = (left + right)/2; 
// Partition the array so that everything to the left of the pivot 
// index is less than or equal to the pivot, and everything to 
// the right of the pivot is greater than or equal to the pivot. 
int newPivIndex = Partition(array, left, right, PivIndex); 
// Recursively sort each half. 
DoQuickSort(ref array, left, newPivIndex - 1); 
DoQuickSort(ref array, newPivIndex + 1, right); 

OK, maintenant, quelque part ici il y a un bug. Où? Commencez à énumérer les faits que vous croyez être vrais, et écrivez une affirmation pour chaque fait. Ecrivez-vous des méthodes d'assistance, comme AllLessThan, qui vérifient les assertions pour vous.

// Choose a pivot halfway along the portion of the list I am searching. 
int PivIndex = (left + right)/2; 

int pivotValue = array[PivIndex]; 
// Partition the array so that everything to the left of the pivot 
// index is less than or equal to the pivot, and everything to 
// the right of the pivot is greater than or equal to the pivot. 
int newPivIndex = Partition(array, left, right, PivIndex); 
Debug.Assert(array[newPivIndex] == pivotValue); 
Debug.Assert(AllLessThanOrEqual(array, left, newPivIndex, pivotValue)); 
Debug.Assert(AllGreaterThanOrEqual(array, newPivIndex, right, pivotValue)); 
// Recursively sort each half. 
DoQuickSort(ref array, left, newPivIndex - 1); 
Debug.Assert(IsSorted(array, left, newPivIndex)); 
DoQuickSort(ref array, newPivIndex + 1, right); 
Debug.Assert(IsSorted(array, left, right)); 

Maintenant, lorsque vous exécutez à nouveau ce programme, le moment de vos affirmations est violée, vous obtiendrez une boîte qui apparaît pour vous dire ce que la nature du bogue est. Continuez à faire cela, en documentant vos conditions préalables et post-conditions avec des assertions jusqu'à ce que vous trouviez le bug.