Quicksort no validar correctamente

Question

El intento de aprender de hacer una implementación de la ordenación rápida, no puedo averiguar por qué no es clasificar correctamente.

Usando esta secuencia:

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

Devuelve la siguiente:

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

Parece para ordenar un poco, pero no todos. ¿Qué me he perdido?

Aquí está mi código:

 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

Además de mi comentario sobre la misma cuestión, quería señalar que los métodos Swap() y DoQuickSort() no tienen que devolver la matriz (como por mi nota en el comentario que explica que la matriz es una referencia en sí). A tal efecto, el código para hacer el trabajo debe ser similar a la siguiente:

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

¿Usted está pidiendo ser entregado a un pez, o que se enseñó a los peces?

Aprendizaje cómo depurar sus propios programas, en lugar de depender de otras personas para que lo haga por usted, es una habilidad que le será muy útil en el futuro.

Cuando nos enfrentamos a este problema, lo primero que me gustaría hacer es marcar el código con comentarios que indica el semántica propósito de cada sección de código:

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

Bien, ahora, en algún lugar de aquí hay un error. ¿Dónde? Empezar a enumerar los hechos que usted cree que es verdad, y escribir una afirmación para cada hecho. Escribe métodos de ayuda a sí mismo, como AllLessThan, que verifican las afirmaciones para usted.

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

Ahora, cuando se ejecuta este programa de nuevo, el momento una de sus afirmaciones es violada, obtendrá un cuadro que aparece para decirle lo que la naturaleza del error es. Sigue haciendo eso, la documentación de sus condiciones previas y condiciones posteriores con las afirmaciones hasta que encuentre el error.

Answer 3

En el método de Partition tiene un rango de bucle equivocado:

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

En caso de llegar a ser:

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

Wikipedia relacionado artículo que 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

Aviso: left ≤ i < right