Pergunta

Eu gostaria de classificar um array em ordem crescente usando C/C++.O resultado é uma matriz contendo índices de elementos.Cada índice é correspondente à localização do elemento na matriz classificada.

Exemplo

Input:  1, 3, 4, 9, 6
Output: 1, 2, 3, 5, 4

Editar: Estou usando o procedimento de classificação de shell.Os índices de valores duplicados são escolhidos arbitrariamente com base nos valores duplicados que aparecem primeiro na matriz original.

Atualizar:

Apesar dos meus melhores esforços, não consegui implementar um algoritmo de classificação para uma série de ponteiros.O exemplo atual não será compilado.

Alguém poderia me dizer o que há de errado?

Eu apreciaria muito alguma ajuda!

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];    //the problem lies somewhere in here
                &pArray[j + 1] = &temp;
                flag = 1;    // indicates that a swap occurred.
            }
        }
    }
};
Foi útil?

Solução

Como você está usando C++, eu faria algo assim.O SortIntPointers função pode ser qualquer algoritmo de classificação, a parte importante é que ela classifica a matriz de ponteiros com base no int que eles estão apontando.Feito isso, você pode percorrer o array de ponteiros e atribuir seu índice classificado, que terminará na posição original no array original.

int* intArray; // set somewhere else
int arrayLen;  // set somewhere else  

int** pintArray = new int*[arrayLen];
for(int i = 0; i < arrayLen; ++i)
{
    pintArray[i] = &intArray[i];
}

// This function sorts the pointers according to the values they
// point to. In effect, it sorts intArray without losing the positional
// information.
SortIntPointers(pintArray, arrayLen);

// Dereference the pointers and assign their sorted position.
for(int i = 0; i < arrayLen; ++i)
{
    *pintArray[i] = i;
}

Espero que isso esteja claro o suficiente.

Outras dicas

Ok, aqui está minha tentativa em C++

#include <iostream>
#include <algorithm>

struct mycomparison
{
    bool operator() (int* lhs, int* rhs) {return (*lhs) < (*rhs);}
};

int main(int argc, char* argv[])
{
    int myarray[] = {1, 3, 6, 2, 4, 9, 5, 12, 10};
    const size_t size = sizeof(myarray) / sizeof(myarray[0]);
    int *arrayofpointers[size];
    for(int i = 0; i < size; ++i)
    {
        arrayofpointers[i] = myarray + i;
    }
    std::sort(arrayofpointers, arrayofpointers + size, mycomparison());
    for(int i = 0; i < size; ++i)
    {
        *arrayofpointers[i] = i + 1;
    }
    for(int i = 0; i < size; ++i)
    {
        std::cout << myarray[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

crie um novo array com valores crescentes de 0 a n-1 (onde n é o comprimento do array que você deseja classificar).Em seguida, classifique a nova matriz com base nos valores da matriz antiga indexados pelos valores da nova matriz.

Por exemplo, se você usar a classificação por bolha (fácil de explicar), então, em vez de comparar os valores na nova matriz, você compara os valores na matriz antiga na posição indexada por um valor na nova matriz:

function bubbleRank(A){
  var B = new Array();
  for(var i=0; i<A.length; i++){
    B[i] = i;
  }
  do{
    swapped = false;
    for(var i=0; i<A.length; i++){
      if(A[B[i]] > A[B[i+1]]){
        var temp = B[i];
        B[i] = B[i+1];
        B[i+1] = temp;
        swapped = true;
      }
    }
  }while(swapped);
  return B;
}

Bem, existe uma solução trival n^2.

Em python:

newArray = sorted(oldArray)
blankArray = [0] * len(oldArray)
for i in xrange(len(newArray)):
  dex = oldArray.index(newArray[i])
  blankArray[dex]  = i

Dependendo do tamanho da sua lista, isso pode funcionar.Se sua lista for muito longa, você precisará fazer uma estranha classificação paralela de array, o que não parece muito divertido e é uma maneira rápida de introduzir bugs extras em seu código.

Observe também que o código acima assume valores exclusivos em oldArray.Se não for esse o caso, você precisará fazer algum pós-processamento para resolver os valores vinculados.

Classificação paralela de vetor usando boost::lambda...

   std::vector<int> intVector;
   std::vector<int> rank;

   // set up values according to your example...
   intVector.push_back( 1 );
   intVector.push_back( 3 );
   intVector.push_back( 4 );
   intVector.push_back( 9 );
   intVector.push_back( 6 );


   for( int i = 0; i < intVector.size(); ++i )
   {
      rank.push_back( i );
   }

   using namespace boost::lambda;
   std::sort( 
              rank.begin(), rank.end(),
              var( intVector )[ _1 ] < var( intVector )[ _2 ] 
            );

   //... and because you wanted to replace the values of the original with 
   //    their rank
   intVector = rank;

Observação:Usei vetoresS em vez de arrays porque é mais claro/fácil, além disso, usei indexação estilo C que começa a contar a partir de 0, não de 1.

crie um novo Array e use o bubble sort para classificar os elementos

int arr[n];
int rank[n];
 for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
       if(arr[i]>arr[j])
         rank[i]++;

A classificação de cada elemento será classificação[i]+1 na ordem de 1,2,....n

Esta é uma solução em linguagem c

#include <stdio.h>

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++)

        // Last i elements are already in place
        for (j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

/* Function to print an array */
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 98};
    int arr_original[] = {64, 34, 25, 12, 22, 11, 98};
    int rank[7];

    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    //PLACE RANK
    //look for location of number in original array
    //place the location in rank array
    int counter = 1;
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++){
            printf("Checking..%d\n", i);
            if (arr_original[i] == arr[k]){
                rank[i] = counter;
                counter++;
                printf("Found..%d\n", i);
            }
        }
    }

    printf("Original array: \n");
    printArray(arr_original, n);

    printf("Rank array: \n");
    printArray(rank, n);
    return 0;
}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top