Come posso ordinare una serie di puntatori doppi in base ai valori a cui puntano?

Question

Sto cercando di creare una funzione in C/C++ per ordinare un array e sostituire ciascun valore con il suo "punteggio" o rango.Accetta un array di puntatori doppi in un array di numeri interi e ordina i puntatori doppi in base al valore dereferenziato degli interi.Ho provato diverse volte a farlo funzionare, ma non riesco a farlo giù.Ancora una volta, deve ordinare i doppi puntatori in base ai valori a cui puntano.Questo è quello che ho:

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

Sei vicino.Stai facendo riferimento all'indirizzo degli elementi dell'array quando esegui lo scambio, il che non è necessario.Gli elementi nell'array sono puntatori ed è ciò che deve essere scambiato.

Vedi sotto:

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.
            }
        }
    }
}

Inoltre, controlla questo bellissimo post sul blog sul Bubble Sorting nel caso tu sia interessato (scusate, spina spudorata :)).Spero di esserti stato d'aiuto con i compiti ;)

---

Modificare:Nota la sottile "ottimizzazione" in cui conti indietro dalla lunghezza dell'array e incrementi solo fino a "i" nel ciclo interno.Ciò ti evita di dover analizzare inutilmente elementi che sono già stati ordinati.

Answer 2

Eh, questi non sono compiti.

In tal caso, considera l'utilizzo di STL per gestire gli array e l'ordinamento.È più facile da sviluppare e mantenere e l'algoritmo std::sort è asintoticamente più veloce del bubble sort.

Answer 3

Dovresti considerare l'utilizzo std::swap() per fare il tuo scambio.Se lo fai, chiamalo così:

swap( obj1, obj2 );

piuttosto che:

std::swap( obj1, obj2 );

Poiché la prima semantica chiamante consentirà la corretta ricerca dello spazio dei nomi per trovare l'overload corretto, se ne esiste uno.Assicurati di avere:

using namespace std;

O:

using std::swap;

in qualche luogo.

Answer 4

Hmm, non ho molta esperienza con STL.Potresti fare un esempio?

Questo programma crea un vettore di int, lo ordina e visualizza i risultati.

#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

Per completare il post di Brian Ensink troverete l'STL pieno di sorprese.Ad esempio, l'algoritmo std::sort:

#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;
}

La prima stampa dell'array mostrerà indirizzi non ordinati.La seconda, dopo l'ordinamento, mostrerà gli indirizzi ordinati.Sul mio compilatore abbiamo:

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

Dai un'occhiata all'intestazione <algoritmo> di STL http://www.cplusplus.com/reference/algoritmo/Troverai molte utilità.Tieni presente che hai altre implementazioni di contenitori che potrebbero adattarsi meglio a te (std::list?std::mappa?).