Как я могу отсортировать массив двойных указателей на основе значений, на которые они указывают?
Вопрос
Я пытаюсь создать функцию на 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.
}
}
}
}
Решение
Ты уже близко.Вы ссылаетесь на адрес элементов массива при замене, что необязательно.Элементы в массиве являются указателями, и это то, что нужно поменять местами.
Смотрите ниже:
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' во внутреннем цикле.Это избавит вас от ненужного повторного анализа элементов, которые уже были отсортированы.
Другие советы
Хех, это не домашнее задание.
Если это так, то рассмотрите возможность использования STL для управления массивами и сортировки.Его проще разрабатывать и поддерживать, а алгоритм std::sort асимптотически быстрее, чем пузырьковая сортировка.
Вам следует рассмотреть возможность использования std::swap()
чтобы произвести вашу замену.Если вы это сделаете, назовите это так:
swap( obj1, obj2 );
вместо того , чтобы:
std::swap( obj1, obj2 );
Поскольку первый вызов semantic позволит правильному поиску в пространстве имен найти правильную перегрузку, если таковая существует.Обязательно имейте при себе либо:
using namespace std;
или:
using std::swap;
где-нибудь.
Хм, у меня не так уж много опыта работы с 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;
}
}
Чтобы завершить пост Брайана Энсинка, вы обнаружите, что 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:: карта?).