Schnelles Sortieren mit Zeigern

Muss ich code ein quick-sort-Algorithmus in C als Hausaufgabe. Dies ist der Prototyp, den ich gegeben wurde:

static inline
int* choose_pivot(int *left, int *right) {
    /* FIX ME */
}

/*
 * partition(left, right, pivot): push value less than *pivot on the left
 * return the new pivot.
 */
 int* partition(int *left, int *right, int *pivot) {
     /* FIX ME */
 } 

 /*
 * quick_sort(left, right)
 */
 void quick_sort(int *left, int *right) {
     /* FIX ME */
 }

wo left ist der Zeiger auf das erste element des Arrays und right wird der Zeiger auf das Letzte element (ausgeschlossen). Ich schrieb den folgenden code:

static inline
int* choose_pivot(int *left, int *right) {
    return &left[(right - left)/2];
}

void swap(int *a, int *b) {
    int c = *a;
    *a = *b;
    *b = c;
}  

int* partition(int *left, int *right, int *pivot) {
    int *i, *q;
    q = right;
    i = left ;
    while ( q > pivot ) {
        while ( pivot < i )
            pivot++;
        while ( q > i )
            q--;
        if ( *q > *pivot ) {
           swap(pivot,q);
        }
    }
    swap(left, q);
    return q ;
}

void quick_sort(int *left, int *right) {
    if(left >= right)
        return;

    int *pivot = partition(left, right, choose_pivot(left, right));
    quick_sort(left, pivot-1);
    quick_sort(pivot + 1, right);
}

Ich bin mit Art 3 des tests: auf einem sortierten array, ein auf einer Rückseite sortiert und
eine auf der Rückseite sortiert ein. den ersten test gut funktioniert, aber die zweite und derjenigen, schlägt fehl. Im Grunde Sinn der Funktionen nicht funktioniert. Ich finde keine Dokumentation, was soll ich tun, da alle quick-sort-Algorithmus verwendet, dessen Länge statt einen Zeiger auf das Letzte element und ich konnte nicht passen die, die ich gefunden habe, die meine Darstellung. Was läuft hier falsch?

EDIT:

Meine neue partition-Funktion sieht nun wie folgt aus, nachdem die Kommentare:

int* partition(int *left, int *right, int *pivot) {
    int *i, *q;
    q = right;
    i = left ;
    int p = *pivot;

    while ( q > pivot ) {
        while ( p < *i )
            pivot++;
        while ( *q > *i )
            q--;
        if ( q > pivot ) {
            swap(pivot,q);
        }
    }

    swap(left, q);
    return q ;
}

Warum sind Sie erhöht die pivot?
Sorry, ich habe versucht, die Anpassung der code hier.
Normalerweise würden Sie verwenden das linke element als pivot. Wenn Sie wählen, um das mittlere element als pivot (zur Handhabung von vorsortierten Listen besser), würden Sie vertauschen die am weitesten Links stehende element vor dem partitionieren. Es scheint, wie Sie haben gelernt, diese an einem gewissen Punkt, denn ich sehe swap(left, q); am Ende der Partitionierungs-Funktion, die nur dann Sinn macht, wenn die pivot-waren die am weitesten Links stehende element. Edit: im code verknüpft, der Drehpunkt ist die am weitesten Links stehende element (i = a[lower]).
Nach einem Blick, die partition-Funktion hat durchaus ein paar Probleme. Sie vergleichen Zeigern anstelle von vergleichen der Werte: pivot < i sollte *pivot < *i. Aber besser noch, halten Sie den pivot-Wert in einer Variablen, die int pivotVal = *pivot;.
Wo soll ich vergleichen die Werte anstelle der Zeiger?
In dem code, den Sie verlinkt sind, gibt es 4 Vergleiche in der partition-Funktion: while ( q >= p ) ist ein index-Vergleich (Zeiger im code) while ( a[p] < i ) ist-Wert-Vergleich, while ( a[q] > i ) ist-Wert-Vergleich, if ( q > p ) ist ein index-Vergleich (Zeiger).

InformationsquelleAutor user26830 | 2014-10-31

Ist hier die einfache Funktion der schnellen Sorte mit Zeigern..

quicksort( void *a, int low, int high )
  {
  int pivot;
  /* Termination condition! */
  if ( high > low )
    {
    pivot = partition( a, low, high );
    quicksort( a, low, pivot-1 );
    quicksort( a, pivot+1, high );
    }
  }

Funktion von Partition

int partition( void *a, int low, int high )
  {
  int left, right;
  void *pivot_item;
  pivot_item = a[low];
  pivot = left = low;
  right = high;
  while ( left < right ) {
    /* Move left while item < pivot */
    while( a[left] <= pivot_item ) left++;
    /* Move right while item > pivot */
    while( a[right] > pivot_item ) right--;
    if ( left < right ) SWAP(a,left,right);
    }
  /* right is final position for the pivot */
  a[low] = a[right];
  a[right] = pivot_item;
  return right;
  }

Hoffe, das hilft!!

Vielen Dank für Ihre Antwort, aber das ist nicht, wie ich soll es tun. Der quick-sort-Funktion muss ein Zeiger auf das erste element und das Letzte element (ausgeschlossen) des Arrays.Es ist ausdrücklich in der Frage.

InformationsquelleAutor Blackhat002

void quick_sort (int *a, int n) {
    if (n < 2)
        return;
    int p = a[n / 2];
    int *l = a;
    int *r = a + n - 1;
    while (l <= r) {
        if (*l < p) {
            l++;
        }
        else if (*r > p) {
            r--;
        }
        else {
            int t = *l;
            *l = *r;
            *r = t;
            l++;
            r--;
        }
    }
    quick_sort(a, r - a + 1);
    quick_sort(l, a + n - l);
}

int main () {
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
    int n = sizeof a / sizeof a[0];
    quick_sort(a, n);
    printf("%d", a[]);
    return 0;
}


// [1]: https://www.cse.ust.hk/~dekai/271/notes/L01a/quickSort.pdf
// [2]: http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html
 //[3]: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

InformationsquelleAutor AVIK DUTTA

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.