Come si fa a rango di una matrice (ordinamento) con valore?*Con un tocco*

Question

Vorrei ordinare un array in ordine crescente utilizzo C/C++.Il risultato è un array che contiene gli indici degli elementi.Ogni indice è corespondent alla posizione dell'elemento nell'array ordinato.

Esempio

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

Edit: Sto usando la shell sort procedura.Il valore duplicato indici sono arbitrariamente scelti in base alla quale i valori duplicati vengono prima dell'array originale.

Aggiornamento:

Nonostante i miei sforzi, non sono stato in grado di implementare un algoritmo di ordinamento di un array di puntatori.L'esempio attuale non viene compilata.

Qualcuno potrebbe dirmi cosa c'è di sbagliato?

Apprezzerei qualche aiuto!

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

Dal momento che si sta utilizzando C++, vorrei fare qualcosa di simile a questo.Il SortIntPointers funzione può essere di qualsiasi algoritmo di ordinamento, la parte importante è che ordina l'array di puntatori basato sul int che fanno per.Una volta fatto questo, si può passare attraverso la matrice di puntatori e assegnare loro ordinato indice che andrà a finire nella posizione originale dell'array originale.

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

Speriamo che sia abbastanza chiaro.

Answer 2

Ok, ecco il mio tentativo in 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 3

creare un nuovo array con valori crescenti da 0 a n-1 (dove n è la lunghezza dell'array da ordinare).Quindi ordinare il nuovo array in base ai valori del vecchio array indicizzato per i valori della nuova matrice.

Per esempio, se si utilizza l'ordinamento a bolle (facile da spiegare), quindi invece di confrontare i valori della nuova matrice, si confrontano i valori del vecchio array alla posizione indicizzata da un valore in un array:

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

Beh, ci sono un trival n^2 soluzione.

In python:

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

A seconda di quanto grande la vostra lista è, questo può funzionare.Se l'elenco è molto lungo, è necessario fare qualche strano parallelo ordinamento degli array, che non sembra molto divertente ed è un modo rapido per introdurre ulteriori bug nel codice.

Si noti inoltre che il codice di cui sopra, assume valori univoci in oldArray.Se non è questo il caso, avrete bisogno di fare un po ' di elaborazione per risolvere legata valori.

Answer 5

In parallelo l'ordinamento di un vettore mediante 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:Ho usato vettori invece di matrici, perché è più chiaro/più facile, inoltre, ho usato il C stile di indicizzazione che inizia a contare da 0, non da 1.

Answer 6

creare un nuovo Array e l'uso di ordinamento a bolle per classificare gli elementi

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]++;

Il rango di ogni elemento di rango[i]+1 per essere nell'ordine di 1,2,....n

Answer 7

Questa è una soluzione in linguaggio 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;
}