Wie macht man Rang eines Arrays (Sortierung) von Wert?*With a twist*

Question

Ich möchte ein array Sortieren in aufsteigender Reihenfolge C/C++.Das Ergebnis ist ein array, element-Indizes.Jeder index ist korrespondente, um das element Position in der sortierten array.

Beispiel

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

Edit: Ich bin mit shell sort-Verfahren.Der doppelte Wert Indizes sind willkürlich gewählt, die doppelte Werte werden zuerst in das ursprüngliche array.

Update:

Trotz meiner Bemühungen, habe ich nicht umsetzen können, ein Sortier-Algorithmus für ein array von Zeigern.Das aktuelle Beispiel wird nicht kompiliert.

Könnte mir bitte jemand sagen was falsch ist?

Ich würde es sehr schätzen einige Hilfe!

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

Da Sie mit C++, ich würde es tun, so etwas wie dieses.Die SortIntPointers Funktion können Sie jede Art Algorithmus, der wichtige Teil ist, dass es sortiert das array von Zeigern auf der Grundlage der int Sie verwiesen.Sobald das erledigt ist, kann man durch das array von Zeigern und ordnen Sie Ihre sortierten index, die am Ende in der ursprünglichen position in das ursprüngliche array.

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

Hoffentlich ist das klar genug.

Answer 2

Ok, hier ist mein atempt 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

erstellen Sie ein neues array mit zunehmenden Werten von 0 bis n-1 (wobei n die Länge des Arrays, die Sie Sortieren möchten).Dann Sortieren Sie die neuen array basierend auf den Werten in den alten indizierten array, indem Sie die Werte in das neue array.

Zum Beispiel, wenn Sie bubble sort (einfach erklärt), dann statt der Vergleich der Werte in das neue array, vergleichen Sie die Werte in das alte array an der position, indiziert durch einen Wert in das neue 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

Nun, es gibt eine trival n^2 Lösung.

In python:

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

Je nachdem, wie groß deine Liste ist, kann dies die Arbeit.Wenn Ihre Kontaktliste sehr lang ist, werden Sie brauchen, um zu tun einige seltsame parallele Arrays Sortieren, die nicht Aussehen wie viel Spaß und ist ein schneller Weg, um die Einführung von extra-bugs in Ihrem code.

Beachten Sie auch, dass der obige code wird davon ausgegangen, eindeutige Werte in oldArray.Wenn das nicht der Fall, müssen Sie zu tun, einige post-processing zu lösen gebunden Werte.

Answer 5

Parallele Sortierung des Vektors mit 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;

Hinweis:Ich Vektoren verwendet, anstelle von arrays, weil es übersichtlicher/einfacher, außerdem habe ich C-style indexing, das beginnt zählen von 0, nicht 1.

Answer 6

erstellen Sie ein neues Array und verwenden Sie bubble-sort, um die Rangfolge der Elemente

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

Der Rang jedes element rank[i]+1 werden in der Reihenfolge 1,2,....n

Answer 7

Dies ist eine Lösung in c-Sprache

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