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

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

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

В python:

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

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

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

Answer 5

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

Примечание:Я использовал векторы вместо массивов, потому что это понятнее / проще, кроме того, я использовал индексацию в стиле C, которая начинает отсчет с 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]++;

Ранг каждого элемента будет равен rank[i] + 1, чтобы быть в порядке 1,2,....n

Answer 7

Это решение на языке си

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