Quicksort non l'ordinamento in modo corretto

Question

Il tentativo di imparare dal fare un'implementazione del Quicksort, non riesco a trovare il motivo per cui non è l'ordinamento in modo corretto.

Con questa sequenza:

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

Si restituisce questo:

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

Sembra di ordinare un po ', ma non tutti. Che cosa ho mancato?

Ecco il mio codice:

 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

Oltre al mio commento sulla questione in sé, ho voluto sottolineare che i metodi Swap() e DoQuickSort() non devono restituire l'array (come per la mia nota nel commento che spiega che l'array è un riferimento per sé). A tal fine, il codice per fare il lavoro dovrebbe essere simile al seguente:

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

Sei chiedendo di essere consegnato un pesce, o di essere insegnato a pescare?

L'apprendimento come eseguire il debug i propri programmi, piuttosto che fare affidamento su altre persone a farlo per voi, è una capacità che vi servirà anche in futuro.

Di fronte a questo problema, la prima cosa che vorrei fare è segnare il codice con commenti che indica il semantica scopo di ogni sezione di codice:

// 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, ora, da qualche parte qui dentro c'è un bug. Dove? Inizia messa in vendita di fatti che si ritiene per essere vero, e scrivere un'affermazione per ogni fatto. Scrivi stessi metodi di supporto, come AllLessThan, che verificano le asserzioni per voi.

// 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));

Ora, quando si esegue nuovamente questo programma, il momento in cui una delle tue affermazioni viene violata, si otterrà una scatola che si apre per dirti quello che la natura del bug è. Continuare a fare questo, documentare i precondizioni e postcondizioni con affermazioni fino a trovare il bug.

Answer 3

Nel vostro metodo di Partition si dispone di una gamma di ciclo sbagliata:

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

Dovrebbe diventare:

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

checkout l'articolo wikipedia correlata che dice:

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

Avviso: left ≤ i < right