كيف رتبة المصفوفة (نوع) من القيمة ؟ *مع تطور*

Question

أود أن نوع صفيف في ترتيب تصاعدي باستخدام C/C++.والنتيجة هي مجموعة تحتوي على عنصر الفهارس.كل مؤشر المراسل إلى عنصر المكان في مجموعة مرتبة.

على سبيل المثال

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

تحرير: أنا باستخدام قذيفة نوع الإجراء.مكررة قيمة الفهارس اختيار تعسفي على أساسها قيم مكررة هي الأولى في المصفوفة الأصلية.

تحديث:

على الرغم من أفضل الجهود ، لم تكن قادرة على تنفيذ خوارزمية الفرز على مجموعة من المؤشرات.الحالي سبيل المثال لا ترجمة.

يمكن شخص من فضلك قل لي ما هو الخطأ ؟

أنني أقدر كثيرا بعض المساعدة!

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

منذ كنت تستخدم C++, وأود أن تفعل شيئا من هذا القبيل.على SortIntPointers وظيفة يمكن أن يكون أي نوع الخوارزمية ، الجزء المهم هو أنه يفرز مجموعة من المؤشرات استنادا إلى int أنها تشير إلى.بمجرد أن يتم ذلك, يمكنك الذهاب من خلال مجموعة من المؤشرات و تعيين فرز الفهرس الذي سوف ينتهي في موقعها الأصلي في المصفوفة الأصلية.

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

نأمل أن هذا واضح بما فيه الكفاية.

Answer 2

حسنا هنا هو بلدي atempt في 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

إنشاء مجموعة جديدة مع زيادة قيم من 0 إلى 1-n (حيث n هو طول المصفوفة كنت ترغب في فرز).ثم فرز مجموعة جديدة تقوم على قيم في مجموعة فهرستها من قبل القيم في مجموعة جديدة.

على سبيل المثال, إذا كنت تستخدم فقاعة نوع (السهل أن أشرح) ، ثم بدلا من مقارنة القيم في مجموعة جديدة ، مقارنة القيم الموجودة في مجموعة في موقف فهرستها من قبل قيمة في مجموعة جديدة:

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

هناك نيفل ن^2 الحل.

في بايثون:

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

اعتمادا على كيفية كبيرة قائمة الخاص بك ، قد يعمل هذا.إذا كان لديك قائمة طويلة جدا, سوف تحتاج إلى القيام ببعض غريب موازية مجموعة الفرز التي لا يبدو مثل الكثير من المرح و هو طريقة سريعة لإدخال إضافية الخلل في التعليمات البرمجية الخاصة بك.

نلاحظ أيضا أن رمز أعلاه يفترض القيم الفريدة في oldArray.إذا كان هذا ليس هو الحال, سوف تحتاج إلى القيام ببعض مرحلة ما بعد المعالجة إلى حل تعادل القيم.

Answer 5

موازية الفرز من ناقلات باستخدام دفعة::امدا...

   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;

ملاحظة:اعتدت ناقلات بدلا من المصفوفات لأنه أوضح/أسهل ، كما اعتدت ج-أسلوب فهرسة والذي يبدأ العد من 0 ، 1.

Answer 6

إنشاء مجموعة جديدة واستخدام نوع فقاعة لترتيب العناصر

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

رتبة كل عنصر سوف تكون رتبة[i]+1 أن يكون في أمر من 1,2,....n

Answer 7

هذا هو الحل في لغة 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;
}