Pregunta

Me gustaría ordenar una matriz en orden ascendente usando C/C++.El resultado es una matriz que contiene índices de elementos.Cada índice corresponde a la ubicación del elemento en la matriz ordenada.

Ejemplo

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

Editar: Estoy usando el procedimiento de clasificación de shell.Los índices de valores duplicados se eligen arbitrariamente en función de qué valores duplicados aparecen primero en la matriz original.

Actualizar:

A pesar de mis mejores esfuerzos, no he podido implementar un algoritmo de clasificación para una serie de punteros.El ejemplo actual no se compilará.

¿Alguien podría decirme qué pasa?

¡Apreciaría mucho un poco de ayuda!

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.
            }
        }
    }
};
¿Fue útil?

Solución

Como estás usando C++, lo haría algo como esto.El SortIntPointers La función puede ser cualquier algoritmo de clasificación, la parte importante es que ordena la matriz de punteros según el int que están señalando.Una vez hecho esto, puede revisar la matriz de punteros y asignar su índice ordenado que terminará en la posición original en la matriz 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;
}

Ojalá quede lo suficientemente claro.

Otros consejos

Ok, aquí está mi intento en 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;
}

cree una nueva matriz con valores crecientes de 0 a n-1 (donde n es la longitud de la matriz que desea ordenar).Luego ordene la nueva matriz según los valores de la matriz anterior indexados por los valores de la nueva matriz.

Por ejemplo, si utiliza la clasificación por burbujas (fácil de explicar), en lugar de comparar los valores en la nueva matriz, compare los valores de la matriz anterior en la posición indexada por un valor en la nueva 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;
}

Bueno, hay una solución trivial n^2.

En pitón:

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

Dependiendo del tamaño de su lista, esto puede funcionar.Si su lista es muy larga, necesitará realizar una extraña ordenación de matrices paralelas, lo cual no parece muy divertido y es una forma rápida de introducir errores adicionales en su código.

También tenga en cuenta que el código anterior asume valores únicos en oldArray.Si ese no es el caso, deberá realizar un procesamiento posterior para resolver los valores vinculados.

Clasificación paralela de vectores 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;

Nota:Utilicé vectoresS en lugar de matrices porque es más claro/fácil, además, utilicé indexación estilo C que comienza a contar desde 0, no 1.

cree una nueva matriz y use la clasificación de burbujas para clasificar los 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]++;

El rango de cada elemento será rango[i]+1 para ser del orden de 1,2,....n

Esta es una solución en lenguaje 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 bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top