Wie kann ich ein Array von Doppelzeigern basierend auf den Werten sortieren, auf die sie zeigen?

Question

Ich versuche eine Funktion in C/C++ zu erstellen, um ein Array zu sortieren und jeden Wert durch seinen "Score" oder Rang zu ersetzen. Es nimmt ein Doppelzeiger-Array zu einem Array von Ints auf und sortiert die Doppelzeiger basierend auf dem dereferenzierten Wert der Ganzzahlen. Ich habe es schon einige Male versucht, um es zum Laufen zu bringen, aber ich bekomme es nicht hin. Erneut muss er die Doppelzeiger basierend auf den Werten sortieren, auf die sie zeigen. Das ist was ich habe:

void SortArray(int ** pArray, int ArrayLength) 
{ 
    int i, j, flag = 1;  // set flag to 1 to begin initial pass 
    int * temp;    // holding variable orig with no * 
    for(i = 1; (i <= ArrayLength) && flag; i++) 
    { 
    flag = 0; 
    for (j = 0; j < (ArrayLength -1); j++) 
    { 
     if (*pArray[j+1] > *pArray[j]) // ascending order simply changes to < 
     { 
      temp = &pArray[j];   // swap elements 
      pArray[j] = &pArray[j+1]; 
      pArray[j+1] = &temp; 
      flag = 1;      // indicates that a swap occurred. 
     } 
    } 
    } 
} 

Answer 1

Sie sind in der Nähe. Sie referenzieren die Adresse der Array-Elemente, wenn Sie tauschen, was nicht notwendig ist. Die Elemente im Array sind Zeiger, und das muss getauscht werden.

Siehe unten:

void SortArray(int ** pArray, int ArrayLength) 
{ 
    int i, j, flag = 1; // set flag to 1 to begin initial pass 
    int * temp;    // holding variable orig with no * 
    for(i = ArrayLength - 1; i > 0 && flag; i--) 
    { 
     flag = 0; 
     for (j = 0; j < i; j++) 
     { 
      if (*pArray[j] > *pArray[j+1])  // ascending order simply changes to < 
      { 
       temp = pArray[j];    // swap elements 
       pArray[j] = pArray[j+1]; 
       pArray[j+1] = temp; 
       flag = 1;    // indicates that a swap occurred. 
      } 
     } 
    } 
} 

Auch Besuche this lovely blog post on Bubble Sorting falls Sie interessiert sind (sorry, schamlose Werbung :)). Hoffe, das hilft Ihnen, Ihre Hausaufgaben;)

---

Edit: Beachten Sie die subtile „Optimierung“, wo man von der Array-Länge zählt zurück und nur bis erhöhen, bis ‚i‘ in der inneren Schleife. Dies erspart Ihnen unnötige Reparaturen von bereits sortierten Artikeln.

Answer 2

Heh, das ist keine Hausaufgaben.

Wenn dies der Fall ist, dann überlegen Sie, die STL zu verwenden, um Arrays zu verwalten und zu sortieren. Es ist einfacher zu entwickeln und zu warten und der std :: sort Algorithmus ist asymptotisch schneller als bubble sort.

Answer 3

Sie sollten std::swap() verwenden, um Ihr Swapping durchzuführen. Wenn Sie das tun, es als solches bezeichnen:

swap(obj1, obj2); 

statt:

std::swap(obj1, obj2); 

Als ersten Aufruf semantische wird der richtige Namespace-Lookup erlaubt die richtige Überlastung zu finden, wenn ein solches vorhanden ist. Achten Sie darauf, entweder haben:

using namespace std; 

oder:

using std::swap; 

irgendwo.

Answer 4

Hmm, ich habe nicht viel Erfahrung mit der STL. Kannst du ein Beispiel geben?

Dieses Programm erstellt einen Vektor von Ints, sortiert es und zeigt die Ergebnisse an.

#include <vector> 
#include <algorithm> 
#include <iostream> 
using namespace std; 

int main() 
{ 
    vector<int>; vec; 
    vec.push_back(7); 
    vec.push_back(5); 
    vec.push_back(13); 
    sort(vec.begin(), vec.end()); 

    for (vector<int>::size_type i = 0; i < vec.size(); ++i) 
    { 
     cout << vec[i] << endl; 
    } 
} 

Answer 5

Um Brian Ensink's Beitrag zu vervollständigen, finden Sie die STL voller Überraschungen. Zum Beispiel der std :: sort-Algorithmus:

Das erste Drucken des Arrays zeigt ungeordnete Adressen. Die zweite, nach der Art, zeigt geordnete Adressen.Auf meinem Compiler, haben wir:

i[0] = 3216087168 
i[1] = 3216087172 
i[2] = 3216087160 
i[3] = 3216087164 
i[4] = 3216087176 

i[0] = 3216087160 
i[1] = 3216087164 
i[2] = 3216087168 
i[3] = 3216087172 
i[4] = 3216087176 

Give <Algorithmus> Header des STL ein Blick http://www.cplusplus.com/reference/algorithm/ Sie werden viele Dienstprogramme finden. Beachten Sie, dass Sie eine andere Implementierung von Containern haben, die Ihnen besser passen könnten (std :: list? Std :: map?).