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

Question

Ich versuche, in C/C++ eine Funktion zu erstellen, um ein Array zu sortieren und jeden Wert durch seinen „Score“ oder Rang zu ersetzen.Es nimmt ein Doppelzeiger-Array in ein Array von Ganzzahlen auf und sortiert die Doppelzeiger basierend auf dem dereferenzierten Wert der Ganzzahlen.Ich habe einige Male versucht, es zum Laufen zu bringen, aber es gelingt mir nicht.Auch hier müssen die Doppelzeiger nach den Werten sortiert werden, auf die sie zeigen.Das habe ich:

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

Du bist nah dran.Sie verweisen beim Austausch auf die Adresse der Array-Elemente, was nicht erforderlich ist.Die Elemente im Array sind Zeiger, und diese müssen ausgetauscht 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.
            }
        }
    }
}

Schauen Sie sich auch um dieser schöne Blog-Beitrag zum Thema Blasensortierung falls es dich interessiert (sorry, schamloser Stecker :)).Ich hoffe, das hilft dir bei deinen Hausaufgaben ;)

---

Bearbeiten:Beachten Sie die subtile „Optimierung“, bei der Sie von der Array-Länge aus zurückzählen und in der inneren Schleife nur bis „i“ hochzählen.Dies erspart Ihnen das unnötige erneute Parsen bereits sortierter Elemente.

Answer 2

Heh, das sind keine Hausaufgaben.

Wenn dies der Fall ist, sollten Sie erwägen, die STL zum Verwalten und Sortieren von Arrays zu verwenden.Es ist einfacher zu entwickeln und zu warten und der std::sort-Algorithmus ist asymptotisch schneller als die Blasensortierung.

Answer 3

Sie sollten über die Verwendung nachdenken std::swap() um deinen Tausch zu machen.Wenn ja, nennen Sie es so:

swap( obj1, obj2 );

statt:

std::swap( obj1, obj2 );

Da die erste aufrufende Semantik es der richtigen Namespace-Suche ermöglicht, die richtige Überladung zu finden, falls eine vorhanden ist.Stellen Sie sicher, dass Sie Folgendes haben:

using namespace std;

oder:

using std::swap;

irgendwo.

Answer 4

Hmm, ich habe nicht viel Erfahrung mit dem STL.Können Sie ein Beispiel nennen?

Dieses Programm erstellt einen Vektor von Ints, sortiert ihn 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 den Beitrag von Brian Ensink zu vervollständigen, finden Sie die STL voller Überraschungen.Zum Beispiel der std::sort-Algorithmus:

#include <iostream>
#include <vector>
#include <algorithm>

void printArray(const std::vector<int *> & p_aInt)
{
   for(std::vector<int *>::size_type i = 0, iMax = p_aInt.size(); i < iMax; ++i)
   {
      std::cout << "i[" << static_cast<int>(i) << "] = " << reinterpret_cast<unsigned     int>(p_aInt[i]) << std::endl ;
   }

   std::cout << std::endl ;
}


int main(int argc, char **argv)
{
   int a = 1 ;
   int b = 2 ;
   int c = 3 ;
   int d = 4 ;
   int e = 5 ;

   std::vector<int *> aInt ;

   // We fill the vector with variables in an unordered way
   aInt.push_back(&c) ;
   aInt.push_back(&b) ;
   aInt.push_back(&e) ;
   aInt.push_back(&d) ;
   aInt.push_back(&a) ;

   printArray(aInt) ; // We see the addresses are NOT ordered
   std::sort(aInt.begin(), aInt.end()) ; // DO THE SORTING
   printArray(aInt) ; // We see the addresses are ORDERED

   return EXIT_SUCCESS;
}

Beim ersten Ausdruck des Arrays werden ungeordnete Adressen angezeigt.Der zweite, nach der Sortierung, zeigt geordnete Adressen an.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

Werfen Sie einen Blick auf den <algorithm>-Header von STL http://www.cplusplus.com/reference/algorithm/Sie werden viele Dienstprogramme finden.Beachten Sie, dass Sie andere Implementierungen von Containern haben, die besser zu Ihnen passen könnten (std::list?std::map?).