C randomisierte pivot-quicksort (Verbesserung der Funktion partition)

Ich bin ein informatik-student (gerade begonnen) war ich auf das schreiben von pseudocode eine pivot-randomisierte version von Quicksort. Habe ich schon geschrieben und getestet und es funktioniert alles perfekt aber...

Die partition Teil sieht ein bisschen zu kompliziert, wie es sich anfühlt, habe ich etwas verpasst oder overthought. Ich kann nicht verstehen, wenn es ok ist, oder wenn ich machte einige vermeidbare Fehler.

Also lange Rede, kurzer Sinn: es funktioniert, aber wie man es besser machen?

Vielen Dank im Voraus für alle die helfen

void partition(int a[],int start,int end)
{
    srand (time(NULL));
    int pivotpos = 3;   //start + rand() % (end-start);
    int i = start;    //index 1
    int j = end;      //index 2
    int flag = 1;
    int pivot = a[pivotpos];   //sets the pivot's value
    while(i<j && flag)      //main loop
    {
        flag = 0;
        while (a[i]<pivot)
        {
            i++;
        }
        while (a[j]>pivot)
        {
            j--;
        }
        if(a[i]>a[j]) //swap && sets new pivot, and restores the flag
        {
            swap(&a[i],&a[j]);
            if(pivotpos == i)
                pivotpos = j;
            else if(pivotpos == j)
                pivotpos = i;
            flag++;
        }
        else if(a[i] == a[j])       //avoids getting suck on a mirror of values (fx pivot on pos 3 of : 1-0-0-1-1)
        {
            if(pivotpos == i) 
                j--;
            else if(pivotpos == j)
                i++;
            else
            {
                i++;
                j--;
            }
            flag++;
        }
    }
}
Wo ist der code, der für die verwürfelung der pivot?
int pivotpos = 3; (gewählt fairen Würfel)
Siehe p2p.wrox.com/visual-c/66347-quick-sort-c-code.html
Warum dieser und nicht mit dem median einer Stichprobe, wie median-von-drei (ersten, mittleren, letzten; Sie zu Sortieren, wählen Sie neue Mitte als pivot. Hat den Vorteil, dass die natürlichen Wächter für die Partitionierung.) Check-out Bentely und McIllroy "Engineering eine Art Funktion" Software: - Praxis und Erfahrung 23:11 (Nov 1993), S. 1249-1265.

InformationsquelleAutor user3236524 | 2014-01-26

  1. 4

    Dies ist der pseudo-code des partition() aus Einführung in Algorithmen , die aufgerufen wird, Lomuto - Partitioning-Algorithmus, und es gibt eine gute Erklärung unten in dem Buch.

    PARTITION(A, p, r)
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r - 1
4   do if A[j] ≤ x
5       then i ←i + 1
6           exchange A[i] ↔ A[j]
7 exchange A[i + 1] ↔ A[r]
8 return i +1

    Implementieren Sie eine randomisierte partition Umsetzung leicht auf der Grundlage der pseudo-code oben. Wie der Kommentar wies darauf hin, bewegen Sie den srand() aus der partition.

    //srand(time(NULL));
int partition(int* arr, int start, int end)
{
    int pivot_index = start + rand() % (end - start + 1);
    int pivot = arr[pivot_index ];

    swap(&arr[pivot_index ], &arr[end]); //swap random pivot to end.
    pivot_index = end;
    int i = start -1;

    for(int j = start; j <= end - 1; j++)
    {
        if(arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[pivot_index]); //place the pivot to right place

    return i + 1;
}

    Ist und die andere partition-Methode erwähnt in dem Buch, die sogenannte Hoare - Partitionierung-Algorithmus, der pseudo-code ist wie folgt:

    Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

    Nachdem Sie die partition, die jedes element in A[p...j] ≤ jedes element in A[j+1...r]. Also den quicksort wäre:

    QUICKSORT (A, p, r)
if p < r then
 q = Hoare-Partition(A, p, r)
 QUICKSORT(A, p, q)
 QUICKSORT(A, q+1, r)
    srand() nicht gehören, in der die Partitionsfunktion verwendet einen quicksort-Algorithmus.
    Hoare - partition ist effizienter (weniger Daten bewegen).
    Was ist der Unterschied in deinem ersten Programm mit regelmäßigen quicksort? Berechnen Sie die random-index, aber dann weisen Sie es end sowie die swap-Wert mit arr[end] so ist es wie es nie passiert. Bin ich etwas fehlt?
    Ich weisen end zu pivot_index nach die swap, so, jetzt a[pivot_index] ist zufällig.

    InformationsquelleAutor jfly

  2. 3

    Gibt es mehrere Möglichkeiten, um die partition für quicksort, das folgende wird wahrscheinlich die einfachste, die ich aufbringen kann. In der Regel zwei Schulen der Partitionierung verwendet werden:

    1. Squeeze - klappt beide enden der Sequenz, bis ein entsprechender swap - paar gefunden wird, dann vertauscht zwei Elemente in die richtige Seiten der Trennwand. Nicht trivial zu implementieren, aber kann effizienter sein (reduzierter swap-count), als die alternative...
    2. Die Austragung - verwendet eine einzige Links nach rechts (oder von rechts nach Links) kehren die Werte, vertauschen von Werten zu einer Inkrementierung der pivot-index, der sich bewegt wie der Algorithmus ausgeführt wird. Sehr einfach zu implementieren, wie Sie unten sehen werden.

    Bevorzuge ich den Sweep-Algorithmus für die Leute lernen quicksort und partitionieren nur weil es ist tot-einfach zu implementieren ist. Beide können umgesetzt werden, führen in-place-Partitionierung, wie es der Fall bei der Umsetzung unten. Zu keinem Zeitpunkt, außer in swap() werden Sie sehen, einen Wert, gespeichert in temp-Lagerung.

    Anhand einer zufälligen pivot-Auswahl ist nur ein kleiner Teil davon. Der folgende Code zeigt, wie Sie initialisiert den Zufallszahlen-generator, und zeigt wahrscheinlich die einfachste partition quicksort-Algorithmus und die Verwendung der darin wirst du finden.

    Es demonstriert unter anderem, dass in C/C++, brauchen Sie nicht beide enden einer partition, da einfache Zeiger-Arithmetik verwendet werden kann zum einstellen der "oberen" Hälfte der Scheidewand. Finden Sie die quicksort() Funktion, wie dies geschehen ist.

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *lhs, int *rhs)
{
    if (lhs == rhs)
        return;

    int tmp = *lhs;
    *lhs = *rhs;
    *rhs = tmp;
}

int partition(int ar[], int len)
{
    int i, pvt=0;

    //swap random slot selection to end.
    // ar[len-1] will hold the pivot value.
    swap(ar + (rand() % len), ar+(len-1));
    for (i=0; i<len; ++i)
    {
        if (ar[i] < ar[len-1])
            swap(ar + i, ar + pvt++);
    }

    //swap the pivot value into position
    swap(ar+pvt, ar+(len-1));
    return pvt;
}

void quicksort(int ar[], int len)
{
    if (len < 2)
        return;

    int pvt = partition(ar, len);
    quicksort(ar, pvt++); //note increment. skips pivot slot
    quicksort(ar+pvt, len-pvt);
}


int main()
{
    srand((unsigned int)time(NULL));

    const int N = 20;
    int data[N];

    for (int i=0; i<N; ++i)
    {
        data[i] = rand() % 50 + 1;
        printf("%d ", data[i]);
    }
    puts("");

    quicksort(data, N);

    for (int i=0; i<N; ++i)
        printf("%d ", data[i]);

    puts("");

    return 0;
}

    Ausgabe (variiert natürlich),

    32 49 42 49 5 18 41 48 22 33 40 27 12 47 41 6 50 27 8 7 
5 6 7 8 12 18 22 27 27 32 33 40 41 41 42 47 48 49 49 50

    Hinweis: dies gilt NICHT für modulo-bias für die Verwendung rand() % len, und ehrlich gesagt, es wäre übertrieben, dies zu tun für dieses Beispiel. Wenn es kritisch ist, würde ich einen anderen generator vollständig. Ein herausragende der Diskussion Methoden der Wahl zufälliger pivot-Standorte für quicksort Partitionierung finden Sie unter diesem Beitrag auf dieser Seite, darunter viele links zu verschiedenen Methoden. Ich schlage vor, die überprüfung es.

    InformationsquelleAutor WhozCraig

Schreibe einen Kommentar