Comment trier un tableau de double pointeurs sur la base des valeurs qu'ils point?

Question

Je suis en train de construire une fonction en C/C++ pour le tri d'un tableau et de les remplacer chaque valeur avec son "score" ou de rang.Il prend un double pointeur de tableau dans un tableau d'entiers, et trie les doubles pointeurs basés sur la valeur déréférencée des nombres entiers.J'ai essayé à quelques reprises pour le faire fonctionner, mais ne peux pas descendre.Une fois de plus, il doit trier les doubles pointeurs sur la base des valeurs qu'ils pointent.C'est ce que j'ai:

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

Vous êtes à proximité.Vous faites référence à l'adresse de la table des éléments lorsque vous permutez, ce qui n'est pas nécessaire.Les éléments du tableau sont des pointeurs, et c'est ce qui doit être échangé.

Voir ci-dessous:

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

Aussi, découvrez cette jolie blog sur la Bulle de Tri dans le cas où vous êtes intéressé (désolé, shameless plug :)).Espère que vous aide dans vos devoirs ;)

---

Edit:Notez la subtile de "l'optimisation", où vous faire le compte à rebours à partir de la longueur du tableau et n'augmente que jusqu'à 'je' dans la boucle interne.Cela vous évite de inutilement ré éléments qui ont déjà été triées.

Answer 2

Hé, ce n'est pas de devoirs.

Si c'est le cas, alors envisager l'utilisation de la STL pour gérer des tableaux et de les trier.Il est plus facile de développer et de maintenir et std::algorithme de tri est asymptotiquement plus rapide que le tri à bulles.

Answer 3

Vous devriez envisager d'utiliser std::swap() pour faire votre échange.Si vous le faites, l'appeler comme tel:

swap( obj1, obj2 );

plutôt que:

std::swap( obj1, obj2 );

Le premier appel sémantique permettra à la bonne de l'espace de noms de recherche pour trouver la bonne surcharge si il en existe un.Assurez-vous d'avoir:

using namespace std;

ou:

using std::swap;

quelque part.

Answer 4

Hmm, je n'ai pas beaucoup d'expérience avec le TSL.Pourriez-vous nous donner un exemple?

Ce programme crée un vecteur d'entiers, il trie et affiche les résultats.

#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

Pour compléter Brian Ensink post, vous trouverez la STL plein de surprises.Par exemple, le std::algorithme de tri:

#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 première impression de la matrice se montrer non ordonnée d'adresses.La deuxième, après le tri, montrera commandé adresses.Sur mon compilateur, nous avons:

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

Donner du TSL <algorithm> en-tête d'un coup d'oeil http://www.cplusplus.com/reference/algorithm/ Vous trouverez un grand nombre de services publics.Notez que vous avez d'autres la mise en œuvre de conteneurs qui pourrait vous convenir mieux (std::list?std::map?).