Как я могу отсортировать массив двойных указателей на основе значений, на которые они указывают?

Question

Я пытаюсь создать функцию на C / C ++ для сортировки массива и замены каждого значения его "оценкой" или рангом.Он принимает массив двойных указателей на массив целых чисел и сортирует двойные указатели на основе разыменованного значения целых чисел.Я довольно много раз пытался заставить это работать, но не смог.Опять же, он должен отсортировать двойные указатели на основе значений, на которые они указывают.Это то, что у меня есть:

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];
            pArray[j+1] = &temp;
            flag = 1;                     // indicates that a swap occurred.
        }
    }
  }
}

Answer 1

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

Смотрите ниже:

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 = ArrayLength - 1; i > 0 && flag; i--)
    {
        flag = 0;
        for (j = 0; j < i; j++)
        {
            if (*pArray[j] > *pArray[j+1])      // ascending order simply changes to <
            { 
                temp = pArray[j];             // swap elements
                pArray[j] = pArray[j+1];
                pArray[j+1] = temp;
                flag = 1;               // indicates that a swap occurred.
            }
        }
    }
}

Кроме того, ознакомьтесь этот прекрасный пост в блоге о пузырьковой сортировке на случай, если вам интересно (извините, бесстыжая вилка :)).Надеюсь, это поможет вам с домашним заданием ;)

---

Редактировать:Обратите внимание на тонкую "оптимизацию", когда вы отсчитываете назад от длины массива и увеличиваете только до 'i' во внутреннем цикле.Это избавит вас от ненужного повторного анализа элементов, которые уже были отсортированы.

Answer 2

Хех, это не домашнее задание.

Если это так, то рассмотрите возможность использования STL для управления массивами и сортировки.Его проще разрабатывать и поддерживать, а алгоритм std::sort асимптотически быстрее, чем пузырьковая сортировка.

Answer 3

Вам следует рассмотреть возможность использования std::swap() чтобы произвести вашу замену.Если вы это сделаете, назовите это так:

swap( obj1, obj2 );

вместо того , чтобы:

std::swap( obj1, obj2 );

Поскольку первый вызов semantic позволит правильному поиску в пространстве имен найти правильную перегрузку, если таковая существует.Обязательно имейте при себе либо:

using namespace std;

или:

using std::swap;

где-нибудь.

Answer 4

Хм, у меня не так уж много опыта работы с STL.Не могли бы вы привести пример?

Эта программа создает вектор целых чисел, сортирует его и отображает результаты.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    vector<int>; vec;
    vec.push_back(7);
    vec.push_back(5);
    vec.push_back(13);
    sort(vec.begin(), vec.end());

    for (vector<int>::size_type i = 0; i < vec.size(); ++i)
    {
        cout << vec[i] << endl;
    }
}

Answer 5

Чтобы завершить пост Брайана Энсинка, вы обнаружите, что STL полон сюрпризов.Например, алгоритм std::sort:

#include <iostream>
#include <vector>
#include <algorithm>

void printArray(const std::vector<int *> & p_aInt)
{
   for(std::vector<int *>::size_type i = 0, iMax = p_aInt.size(); i < iMax; ++i)
   {
      std::cout << "i[" << static_cast<int>(i) << "] = " << reinterpret_cast<unsigned     int>(p_aInt[i]) << std::endl ;
   }

   std::cout << std::endl ;
}


int main(int argc, char **argv)
{
   int a = 1 ;
   int b = 2 ;
   int c = 3 ;
   int d = 4 ;
   int e = 5 ;

   std::vector<int *> aInt ;

   // We fill the vector with variables in an unordered way
   aInt.push_back(&c) ;
   aInt.push_back(&b) ;
   aInt.push_back(&e) ;
   aInt.push_back(&d) ;
   aInt.push_back(&a) ;

   printArray(aInt) ; // We see the addresses are NOT ordered
   std::sort(aInt.begin(), aInt.end()) ; // DO THE SORTING
   printArray(aInt) ; // We see the addresses are ORDERED

   return EXIT_SUCCESS;
}

При первой распечатке массива будут показаны неупорядоченные адреса.На втором, после сортировки, будут показаны упорядоченные адреса.В моем компиляторе у нас есть:

i[0] = 3216087168
i[1] = 3216087172
i[2] = 3216087160
i[3] = 3216087164
i[4] = 3216087176

i[0] = 3216087160
i[1] = 3216087164
i[2] = 3216087168
i[3] = 3216087172
i[4] = 3216087176

Дать стл х <algorithm> заголовок взгляд http://www.cplusplus.com/reference/algorithm/ Вы найдете множество утилит.Обратите внимание, что у вас есть другая реализация контейнеров, которая могла бы подойти вам лучше (std::list?std:: карта?).