Hoe kan men een reeks (soort) van waarde te rangschikken? *Met een draai*

stemmen
5

Ik wil graag een array in oplopende volgorde met behulp van sorteren C/C++. Het resultaat is een array met element indices. Elke index is corespondent het element locatie in de gesorteerde array.

Voorbeeld

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

Edit: Ik gebruik shellsort procedure. De dubbele waarde indexen worden willekeurig gekozen op basis waarvan dubbele waarden worden eerst in de oorspronkelijke array.

Bijwerken:

Ondanks mijn best doen, heb ik niet in staat om een ​​sorteer-algoritme te implementeren voor een array van pointers geweest. De huidige voorbeeld zal niet compileren.

Kan iemand mij vertellen wat er mis is?

Ik zou het zeer waarderen wat 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.
            }
        }
    }
};
De vraag is gesteld op 17/08/2008 om 01:13
user
In andere talen...                            


7 antwoorden

stemmen
0

Nou, er is een trival n ^ 2-oplossing.

In python:

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

Afhankelijk van hoe groot de lijst is, kan dit werken. Als de lijst zeer omvangrijk is, moet u een aantal vreemde parallelle reeks sorteren, die er niet uitziet als veel plezier en is een snelle manier om extra bugs te introduceren in uw code te doen.

Merk ook op dat de bovenstaande code aanneemt unieke waarden in oldArray. Als dat niet het geval is, moet u een aantal nabewerking doen om vastgebonden waarden op te lossen.

antwoordde op 17/08/2008 om 01:21
bron van user

stemmen
7

Omdat je met behulp van C ++, zou ik zoiets als dit te doen. De SortIntPointersfunctie kan welke soort algoritme, het belangrijk is dat het sorteert de array van pointers op basis van de intzij verwijzen naar. Zodra dat gebeurd is, kan je door de array van pointers en hun gesorteerde index, die zal eindigen in de oorspronkelijke positie in de oorspronkelijke array toe te wijzen.

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

Hopelijk dat is duidelijk genoeg.

antwoordde op 17/08/2008 om 01:33
bron van user

stemmen
2

maak een nieuw array met toenemende waarden van 0 tot n-1 (waarbij n de lengte van de array die u wilt sorteren). sorteren Dan is de nieuwe array op basis van de waarden in de oude reeks geïndexeerd door de waarden in de nieuwe array.

Bijvoorbeeld, als u bubble sort gebruiken (eenvoudig uit te leggen), dan in plaats van het vergelijken van de waarden in de nieuwe array, de waarden te vergelijken in de oude reeks op de positie geïndexeerd door een waarde in de nieuwe 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;
}
antwoordde op 17/08/2008 om 01:46
bron van user

stemmen
3

Ok, hier is mijn 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;
}
antwoordde op 23/09/2008 om 06:30
bron van user

stemmen
0

Parallel sortering van vector met behulp van 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;

Opmerking: Ik gebruikte vectoren in plaats van arrays, want het is duidelijker / makkelijker, ook, ik gebruikte C-stijl indexering die begint te tellen vanaf 0, niet 1.

antwoordde op 23/09/2008 om 15:23
bron van user

stemmen
0

maak een nieuwe Array en gebruik bubble sort om de elementen te rangschikken

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

De positie van elk element rangschikking [i] 1 om in de orde van 1,2 te zijn, .... n

antwoordde op 18/10/2015 om 05:21
bron van user

stemmen
0

Dit is een 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;
}
antwoordde op 30/05/2017 om 06:23
bron van user

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more