c++ - sort - ¿Cómo se clasifica una matriz(ordenar) por valor?*Con un giro*

sort en c

Question

Me gustaría ordenar una matriz en orden ascendente usando C/C++ . El resultado es una matriz que contiene índices de elemento. Cada índice es corespondiente 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 están 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 indicadores. El ejemplo actual no compilará.

¿Podría alguien decirme qué sucede?

¡Agradecería mucho 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.
            }
        }
    }
};

Answer 1

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

En Python:

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

Dependiendo de qué tan grande sea su lista, esto puede funcionar. Si su lista es muy larga, deberá hacer una selección extraña de arreglos en paralelo, que no parece muy divertida y es una manera 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, tendrás que hacer un postprocesamiento para resolver los valores ligados.

Answer 2

Ya que estás usando C ++, lo haría algo como esto. La función SortIntPointers puede ser cualquier algoritmo de ordenación, la parte importante es que ordena la matriz de punteros en función del int que apuntan. Una vez hecho esto, puede ir a través de 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;
}

Espero que eso sea lo suficientemente claro.

Answer 3

crea una nueva matriz con valores crecientes de 0 a n-1 (donde n es la longitud de la matriz que deseas ordenar). Luego, clasifique la nueva matriz según los valores en la matriz anterior indexada por los valores en la nueva matriz.

Por ejemplo, si usa sort de burbuja (fácil de explicar), en lugar de comparar los valores en la nueva matriz, compara los valores en 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;
}

Answer 4

Clasificación paralela del vector 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 / más fácil, también utilicé la indexación estilo C, que comienza contando desde 0, no 1.

Answer 5

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

Answer 6

crea una nueva matriz y usa la clasificación de burbuja 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á el rango [i] +1 en el orden de 1,2, .... n

Answer 7

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