Como posso classificar uma matriz de ponteiros duplos com base nos valores para os quais eles apontam?

Question

Estou tentando construir uma função em C/C++ para classificar uma matriz e substituir cada valor por sua "pontuação" ou classificação.Ele pega uma matriz de ponteiros duplos para uma matriz de inteiros e classifica os ponteiros duplos com base no valor desreferenciado dos inteiros.Já tentei algumas vezes fazê-lo funcionar, mas não consigo baixá-lo.Mais uma vez, ele deve classificar os ponteiros duplos com base nos valores para os quais apontam.Isto é o que eu tenho:

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

Você está perto.Você está referenciando o endereço dos itens da matriz ao trocar, o que não é necessário.Os itens do array são ponteiros e é isso que precisa ser trocado.

Veja abaixo:

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

Além disso, confira esta adorável postagem no blog sobre Bubble Sorting caso você esteja interessado (desculpe, plug sem vergonha :)).Espero que isso ajude você com sua lição de casa ;)

---

Editar:Observe a "otimização" sutil em que você conta regressivamente a partir do comprimento da matriz e aumenta apenas até 'i' no loop interno.Isso evita que você reveja desnecessariamente itens que já foram classificados.

Answer 2

Heh, isso não é lição de casa.

Se for esse o caso, considere usar o STL para gerenciar matrizes e classificar.É mais fácil de desenvolver e manter e o algoritmo std::sort é assintoticamente mais rápido que o bubble sort.

Answer 3

Você deve considerar usar std::swap() para fazer sua troca.Se você fizer isso, chame-o assim:

swap( obj1, obj2 );

em vez de:

std::swap( obj1, obj2 );

Como a primeira semântica de chamada permitirá que a pesquisa de namespace adequada encontre a sobrecarga correta, se existir.Certifique-se de ter:

using namespace std;

ou:

using std::swap;

em algum lugar.

Answer 4

Hmm, não tenho muita experiência com STL.Você poderia dar um exemplo?

Este programa cria um vetor de ints, classifica-o e exibe os resultados.

#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

Para completar o post de Brian Ensink, você encontrará o STL cheio de surpresas.Por exemplo, o 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;
}

A primeira impressão do array mostrará endereços não ordenados.O segundo, após a classificação, mostrará os endereços ordenados.No meu compilador, temos:

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

Dê uma olhada no cabeçalho <algorithm> do STL http://www.cplusplus.com/reference/algorithm/Você encontrará muitos utilitários.Observe que você tem outra implementação de contêineres que pode ser melhor para você (std::list?std::mapa?).