Hoe 'n skikking (soort) deur waarde rang? * Met 'n draai *

Question

Ek wil graag 'n skikking in stygende volgorde met behulp van C/C++ sorteer. Die uitslag is 'n skikking met element indekse. Elke indeks is correspondent om die element plek in die gesorteerde skikking.

Voorbeeld

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

Edit: Ek gebruik dop soort prosedure. Die dubbele waarde indekse is arbitrêr gekies op grond van wat dupliseer waardes is eerste in die oorspronklike skikking.

Update:

Ten spyte van my beste pogings, ek het nie in staat was om 'n sorteer algoritme vir 'n verskeidenheid van wenke te implementeer nie. Die huidige voorbeeld sal nie saam te stel.

Kan iemand asseblief vir my sê wat is fout?

Ek sal dit baie waardeer enige hulp!

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

Sedert jy gebruik C ++, ek sou dit so iets te doen. Die SortIntPointers funksie kan enige soort algoritme wees, die belangrike deel is dat dit sorteer die skikking van wysers gebaseer op die int dat hulle verwys na. Sodra dit gedoen is, kan jy gaan deur middel van die skikking van wysers en hul gesorteer indeks wys wat sal eindig in die oorspronklike posisie in die oorspronklike skikking.

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

Hopelik is dit duidelik genoeg.

Answer 2

Ok, hier is my poging 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

'n nuwe reeks met 'n toenemende waardes van 0 tot N-1 (waar n die lengte van die skikking wat jy wil uit te sorteer). sorteer dan die nuwe reeks gebaseer op die waardes in die ou verskeidenheid geïndekseer deur die waardes in die nuwe reeks.

Byvoorbeeld, as jy borrel soort gebruik (maklik om te verduidelik), dan in plaas van die vergelyking van die waardes in die nuwe skikking, jy die waardes vergelyk in die ou opgestel by die posisie geïndekseer deur 'n waarde in die nuwe reeks:

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

Wel, daar is 'n trival N ^ 2 oplossing.

In luislang:

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

Afhangende van hoe groot jou lys is, kan dit werk. As jou lys is baie lank, sal jy nodig het om 'n paar vreemde parallel verskeidenheid sorteer, wat nie lyk baie pret en 'n vinnige manier om ekstra foute te voer in jou kode te doen.

Let ook daarop dat die bogenoemde kode veronderstel unieke waardes in oldArray. As dit nie die geval is, moet jy 'n paar post verwerking doen om vasgebind waardes op te los.

Answer 5

Parallel sortering van vektor met behulp hupstoot :: 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;

Let wel:. Ek gebruik vektore in plaas van skikkings, want dit is duidelik / makliker, ook, gebruik ek C-styl kruip wat begin tel van 0, nie 1

Answer 6

'n nuwe Array en gebruik borrel soort aan die elemente rang

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

Die rang van elke element sal rang [i] 1 te wees in die orde van 1,2 .... wees N

Answer 7

Dit is 'n oplossing in c taal

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