Сортировка C ++ Массивы пользовательских объектов с использованием указателей?
Это мой первый вопрос, поэтому, пожалуйста, дайте мне обратную связь не только по этому вопросу, но и по тому, как я его задал (пожалуйста, и спасибо).
В моем последнем задании для CS 201 мы разработали класс, представляющий рейс авиакомпании, он содержит некоторые личные данные:
string airline, originAirport, destinationAirport;
int flightNumber, departureTime, arrivalTime; //times from 0000 to 2359
Частью задания было отображение всех вылетов или прилетов (по выбору пользователя) для одного аэропорта. Для дополнительного кредита, выходные данные должны были быть отсортированы в порядке возрастания (сначала самое раннее время). Инструктор не научил нас, как использовать std :: sort, поэтому идея (я полагаю) заключалась в том, чтобы разработать наш собственный метод сортировки.
Я думал о том, чтобы заполнить массив указателей Flight согласно результатам своего рода; Однако я столкнулся с проблемой. Вот мой код для сортировки:
for(i=0; i<maxArraySize; i++)
{
minIndex = i; //assume that element i is the earliest arrival time
for(j=0; j<maxArraySize; j++) // j=i produced unsorted results
{
if (flightArray[j].getArrivalTime() < flightArray[minIndex].getArrivalTime())
minIndex = j;
} // at the end of this loop, I now have the smallest flight time's index
pointerArray[i] = &flightArray[minIndex];
} //when the loop terminates I *should* have a sorted list of pointers (but I don't)
Я просмотрел выходные данные, чтобы увидеть, в чем проблема, и понял, что все указатели указывают на один и тот же рейс (который действительно имел самое раннее время прибытия). Это привело меня к мысли, что проблема была в том, что мой код не исключал полеты, которые уже были помещены в pointerArray.
За исключением «гашения» полета, на которое я только что указал (что противоречит цели указателя), я не мог найти никакого способа «игнорировать» рейсы, на которые уже были наведены указатели.
Как я могу решить эту проблему?
Я хотел бы прояснить, что я уже решил проблему очень хакерским способом. Я не доволен решением, потому что считаю, что оно не оптимально, но оно работает. Я не пытаюсь сделать так, чтобы мое задание просто помогло мне стать лучшим программистом
Решение
BubbleSort достаточно просто реализовать, даже если он не самый производительный:
- Заполните массив всеми указателями.
- цикл пока все не отсортировано
- Цикл от первого элемента и замена следующего, если их порядок неверен, пока отсортированные элементы не будут достигнуты (в этот момент конечный элемент самый высокий, таким образом отсортированный)
Обратите внимание, что для всех, кроме образовательных целей (или возможной оптимизации), std :: sort следует отдавать предпочтение перед собственными реализациями.
В одном из комментариев говорилось, что пузырьковая сортировка сложна и трудна, поэтому в своем ответе я добавил реализацию алгоритма. Имейте в виду, что особенно конечное условие внутреннего цикла (J < я — 1) должен быть правильным и что направление внешнего и внутреннего цикла должно быть противоположным. И его можно оптимизировать, остановив его, если не было выполнено свопинга, но в первую очередь нас не волновала производительность.
template <typename T>
void bubbleSort(T* arr, int nbr, bool(*comp)(const T& left, const T& right))
{
for (int i = nbr; i > 1; --i)
{
for (int j = 0; j < i-1; ++j)
{
if (!comp(arr[j], arr[j+1])) std::swap(arr[j], arr[j+1]);
}
}
}
Другие решения
В основном вам нужно отсортировать ваш массив. Существует множество алгоритмов сортировки, и вы узнаете важные из них на курсах Структуры данных и Алгоритмы. Оптимальный алгоритм сортировки имеет O (n lg n) (см. Быструю сортировку и сортировку слиянием в Википедии. станд :: сортировать также имеет O (N LG N) сложность времени.
Два простых алгоритма сортировки, которые довольно легко реализовать, это пузырьковая сортировка и вставка. Со вторым, более эффективным на практике (даже при том, что оба O (n2)).
И о вашем стиле вопроса, это хорошо написанный первый вопрос.
PS: Если вы не знаете, что означает O (n), проверьте этот.
РЕДАКТИРОВАТЬ Почему текущий подход не работает, обратите внимание, что внутренний цикл всегда находит минимум всего массива, поэтому он всегда возвращает один и тот же результат.
Вот идея, если вы хотите изменить свой код как можно меньше, при условии, что время прибытия все разные (то есть, не два рейса с одинаковым временем прибытия. Это может быть неотъемлемое значение единый аэропорт в назначении): просто сохраните ранее найденное минимальное время прибытия и присвойте j только minIdex, если время прибытия j-го элемента не равно сохраненному минимуму. Помимо определения переменной, он добавляет только одну строку в ваш код. Я сохраняю реализацию в качестве упражнения.
Другой подход, для массивов с нечеткими значениями, это удалить найденный минимум из массива или установить его значение на максимум. Это, тем не менее, изменяет содержимое массива, поэтому вам сначала нужно сделать его копию.
minIndex всегда будет одинаковым, поэтому pointerArray[i] получит то же значение — адрес minIndex элемент flightArray. Вы не сортируете, вы просто ищете минимальный элемент
Во-первых: была идея, что вы пишете свою собственную функцию сортировки, или
что вы проявляете инициативу поиска и использования
std::sort? (Если это хороший курс, я бы ожидал последнего.)
Если вы хотите написать свой собственный, сортировка вставки, вероятно,
самый простой: у вас есть простой инвариант: массив ниже i является
уже отсортированы, так что вам просто нужно найти позицию для вставки
элемент i в нем (подталкивая любые последующие элементы вверх на один),
и массив ниже i + 1 сейчас отсортировано. Начать с i == 0
(так как массив ниже 0 пусто, это по определению
отсортировано), и работать до тех пор, пока вы не охватите каждый элемент.
Я бы предложил научиться использовать алгоритмы STL. Они имеют очень хорошие характеристики и могут быть объединены для выполнения практически любой задачи.
Вот пример, который должен интегрироваться в существующую структуру данных.
bool CompareArrivalTimes(Flight *left, Flight *right)
{
return left->getArrivalTime() < right->getArrivalTime();
}std::vector<Flight*> SortByArrivalTime(Flight* flightArray, size_t arrayLength)
{
std::vector<Flight*> results;
for(; arrayLength; --arrayLength)
results.push_back(flightArray++);
std::sort(results.begin(), results.end(), CompareArrivalTimes ); // O(N * lg(N)) complexity
return results;
}
Вот пример его использования в некоторых тестовый код.
#include <algorithm>
#include <vector>
#include <iostream>
class Flight
{
private:
// other variables omitted
static int flightCounter;
int arrivalTime;
int flightNumber;
public:
Flight(int arrival) : // constructor for testing only
arrivalTime(arrival),
flightNumber(++flightCounter)
{}
// other methods omitted
int getArrivalTime() { return arrivalTime; }
int getFlightNumber() { return flightNumber; }
};
int Flight::flightCounter = 0;
int main(int argv, char** args)
{
Flight flights[] = {1000, 900, 1630, 1600, 1545, 530, 2200};
size_t numberOfFlights = sizeof(flights)/sizeof(Flight);
std::cout << "Unsorted times" << std::endl;
for(size_t i=0; i < numberOfFlights; ++i)
std::cout << "Flight: "<< flights[i].getFlightNumber() << " Arrival Time: " << flights[i].getArrivalTime() << std::endl;
std::vector<Flight*> sorted = SortByArrivalTime(flights, numberOfFlights);
std::cout << "Sorted times" << std::endl;
for(size_t i=0; i < numberOfFlights; ++i)
std::cout << "Flight: "<< sorted[i]->getFlightNumber() << " Arrival Time: " << sorted[i]->getArrivalTime() << std::endl;
}
Вот вывод
Unsorted times
Flight: 1 Arrival Time: 1000
Flight: 2 Arrival Time: 900
Flight: 3 Arrival Time: 1630
Flight: 4 Arrival Time: 1600
Flight: 5 Arrival Time: 1545
Flight: 6 Arrival Time: 530
Flight: 7 Arrival Time: 2200
Sorted times
Flight: 6 Arrival Time: 530
Flight: 2 Arrival Time: 900
Flight: 1 Arrival Time: 1000
Flight: 5 Arrival Time: 1545
Flight: 4 Arrival Time: 1600
Flight: 3 Arrival Time: 1630
Flight: 7 Arrival Time: 2200