Quicksort non funziona

Question

Questo è tutto il mio codice per il mio metodo Quicksort, funziona su una serie di 21 numeri, ma non sul mio set di dati reali, che è di circa 100000. Non ho idea di ciò che è sbagliato, sono stato giocherellare per due ore e si è dovuto presto! Qualsiasi aiuto sarebbe molto gradito

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

Assunzione:

• un detiene 10'000 campioni,
• partenza è 500

• fine è di 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) );
  

FINE / 4 è di 250

.. che si sta scambiando valori dall'esterno della cernita sottoinsieme .

Answer 2

Questo non sembra un problema compiti a casa. Se fosse un problema compiti a casa, l'autore avrebbe scritto su sette a dieci righe di codice, con una prova di efficacia, e lo ha trasformato in. Questo ragazzo sta cercando di essere di fantasia, e la cosa lo sta mordendo nel didietro. Si può dire dal modo in cui scende dell'inserimento-ordinamento per intervalli cosiddetti "piccoli". (Indizio: la dimensione intervallo di soglia è più della metà le dimensioni dei dati di test Lascia la tua algoritmo di un certo margine di ricorsione se si vuole testare bene..) In secondo luogo, v'è il lavoro supplementare che sta facendo per trovare un perno ideale. Questo tipo di complessità ha un costo.

Questo è un hobbista al lavoro. Quello di cui ha bisogno non è solo una risposta. Ha bisogno di un approccio alla soluzione dei problemi difficili. Quicksort è solo il veicolo per l'educazione.

Ecco il mio approccio.

Il trucco è quello di scrivere Quicksort come Quicksort, farlo funzionare, e poi preoccuparsi di trucchi speciali fantasia. Uccidere il rumore per inserimento classificare piccoli intervalli. Proprio dal presupposto che ogni intervallo di dimensioni pari a zero o uno è già ordinato (che è il vostro caso base) e poi lavorare per rendere il vostro lavoro codice di partizionamento utilizzando l'estremità sinistra dell'intervallo come il perno (come nel classico Quicksort originale), e si potrebbe prendere in considerazione la stampa i risultati dei vostri dati dopo un passaggio di partizionamento come un modo per dimostrare a te stesso che funziona. Potrai sviluppare le competenze di test in questo modo. In ogni caso, una volta che hai un Quicksort lavoro, allora si può fare cose come selezione perno separato in una funzione e giocare con l'implementazione.

In bocca al lupo, e godetevi il vostro progetto. Non dimentichiamo, però:! Vogliamo tempi, e soprattutto il confronto di tempo con la routine di ordinamento della libreria standard