Comment classer (trier) un tableau par valeur ?*Avec une touche d'originalité*

Question

Je voudrais trier un tableau par ordre croissant en utilisant C/C++.Le résultat est un tableau contenant des index d’éléments.Chaque index correspond à l'emplacement de l'élément dans le tableau trié.

Exemple

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

Modifier: J'utilise la procédure de tri shell.Les index de valeurs en double sont arbitrairement choisis en fonction des valeurs en double qui se trouvent en premier dans le tableau d'origine.

Mise à jour:

Malgré tous mes efforts, je n'ai pas réussi à implémenter un algorithme de tri pour un tableau de pointeurs.L'exemple actuel ne sera pas compilé.

Quelqu'un pourrait-il me dire ce qui ne va pas ?

J'apprécierais beaucoup de l'aide !

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

Puisque vous utilisez C++, je ferais quelque chose comme ça.Le SortIntPointers La fonction peut être n'importe quel algorithme de tri, l'important est qu'elle trie le tableau de pointeurs en fonction du int qu'ils désignent.Une fois cela fait, vous pouvez parcourir le tableau de pointeurs et attribuer leur index trié qui se retrouvera à la position d'origine dans le tableau d'origine.

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

J'espère que c'est assez clair.

Answer 2

Ok, voici ma tentative 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 3

créez un nouveau tableau avec des valeurs croissantes de 0 à n-1 (où n est la longueur du tableau que vous souhaitez trier).Triez ensuite le nouveau tableau en fonction des valeurs de l'ancien tableau indexées par les valeurs du nouveau tableau.

Par exemple, si vous utilisez le tri à bulles (facile à expliquer), alors au lieu de comparer les valeurs du nouveau tableau, vous comparez les valeurs de l'ancien tableau à la position indexée par une valeur du nouveau tableau :

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

Eh bien, il existe une solution 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

Selon la taille de votre liste, cela peut fonctionner.Si votre liste est très longue, vous devrez effectuer un étrange tri de tableaux parallèles, ce qui ne semble pas très amusant et constitue un moyen rapide d'introduire des bogues supplémentaires dans votre code.

Notez également que le code ci-dessus suppose des valeurs uniques dans oldArray.Si ce n'est pas le cas, vous devrez effectuer un post-traitement pour résoudre les valeurs liées.

Answer 5

Tri parallèle des vecteurs à l'aide de 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;

Note:J'ai utilisé des vecteurs au lieu de tableaux car c'est plus clair/plus facile. J'ai également utilisé l'indexation de style C qui commence à compter à partir de 0 et non de 1.

Answer 6

créez un nouveau tableau et utilisez le tri à bulles pour classer les éléments

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

Le rang de chaque élément sera rang[i]+1 pour être de l'ordre de 1,2,....n

Answer 7

Ceci est une solution en langage 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;
}