Quicksort no funciona

Question

Todo esto es mi código de mi método de clasificación rápida, funciona en un conjunto de 21 números, pero no en mi conjunto de datos reales, que es aproximadamente 100000. No tengo idea de lo que está mal, he estado jugueteando para dos horas y que se debe pronto! Cualquier ayuda sería muy bienvenido

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

Supuesto:

• A tiene 10'000 muestras,
• inicio es de 500

• final es 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) );
  

final / 4 es de 250

.. sea intercambiando los valores de fuera de su clasificación subconjunto .

Answer 2

Esto no se ve como un problema de tarea. Si fuera un problema de tarea, el autor hubiera escrito sobre siete a diez líneas de código, con una prueba de efectividad, y lo convirtió en. Este chico está tratando de ser de lujo, y le muerde en la parte trasera. Usted puede decir por la forma en que cae de su inserción-tipo para los llamados intervalos "pequeños". (Una pista: el tamaño de intervalo umbral es más de la mitad del tamaño de los datos de prueba Dé su algoritmo de algo de espacio para recursivo si quieres probarlo también..) En segundo lugar, existe el trabajo extra que está haciendo para encontrar un pivote ideal. Este tipo de complejidad tiene un costo.

Este es un aficionado en el trabajo. Lo que necesita no es sólo una respuesta. Se necesita un enfoque para resolver problemas difíciles. Ordenación rápida es sólo el vehículo para que la educación.

Aquí está mi enfoque.

El truco es escribir ordenación rápida como la ordenación rápida, conseguir que funcione, y luego preocuparse de trucos especiales de lujo. Acabar con el ruido acerca de la inserción de clasificación intervalos pequeños. Acaba de asumir que cualquier intervalo de tamaño cero o uno ya está ordenada (que es el caso base) y luego trabajar en hacer su partición trabajo código utilizando el extremo izquierdo del intervalo como el pivote (como en la clásica ordenación rápida original), y es posible que considerar la impresión de los resultados de sus datos después de una pasada de partición como una manera de mostrar a ti mismo que funciona. Que va a desarrollar habilidades de pruebas de esa manera. De todos modos, una vez que tenga una clasificación rápida de trabajo, entonces usted puede hacer cosas como la selección de pivote separados en una función y jugar con la aplicación.

Buena suerte, y disfrutar de su proyecto. No hay que olvidar, sin embargo:! Queremos tiempos, y especialmente comparaciones en el tiempo con la rutina de ordenación en la biblioteca estándar