Как ранжировать массив (сортировать) по значению? * С изюминкой *

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

Хорошо, вот моя попытка в 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 до n-1 (где 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

Это решение на языке 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;
}

Answer 5

создайте новый массив и используйте сортировку по пузырькам для ранжирования элементов

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 6

Параллельная сортировка вектора с использованием 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;

Примечание: я использовал vectorS вместо массивов, потому что он понятнее / проще, также я использовал индексацию в стиле C, которая начинает отсчет с 0, а не с 1.

Answer 7

Ну, есть тривальное n ^ 2 решение.

В питоне:

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

В зависимости от размера вашего списка, это может сработать. Если ваш список очень длинный, вам нужно выполнить странную сортировку параллельных массивов, которая не выглядит забавной и позволяет быстро вносить дополнительные ошибки в код.

Также обратите внимание, что приведенный выше код принимает уникальные значения в oldArray. Если это не так, вам нужно выполнить некоторую постобработку для решения связанных значений.