Sorting C++ Arrays of user-defined objects using Pointers?

Question

This is my first question, so please give me feedback not only on the question but on how I asked it as well (please and thank you).

In my last assignment for CS 201 we designed a class representing an airline flight, it contains some private data:

string airline, originAirport, destinationAirport;
int flightNumber, departureTime, arrivalTime; //times from 0000 to 2359

Part of the assignment was to display all departures or arrivals (as selected by the user) for a single airport. For extra credit, the output was to be sorted in ascending order (earliest time first). The instructor has not taught us how to use std::sort from so the idea (I assume) was to devise our own method of sorting.

My thinking was to fill an array of Flight pointers according to the results of a sort; however I ran into a problem. Here is my code to do the sorting:

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)

I looked over the output to see what the problem was and I realized that all the pointers were pointing to the same flight (which did, indeed, have the earliest arrival time). This led me to believe that the problem was that my code was not excluding flights which had already been placed into pointerArray.

Outside of "blanking" the flight that I just pointed to (which defeats the purpose of the pointer) I could not find any way of "ignoring" flights which already had pointers pointing at them.

How can I have solved this problem?

I would like to make it clear that I have already solved the problem in a very hack-y way. I am not happy with the solution because I feel it is not optimal but it works. I am not attempting to have SO do my assignment, just help to make me a better programmer

Answer 1

Basically you need to sort your array. There are many, many sorting algorithms and you will learn the important ones in Data Structures and Algorithm courses. An optimal sorting algorithm is of O(n lg n) (see quick sort and merge sort in wikipedia. std::sort is also of O(n lg n) time complexity.

Two simple sorting algorithms, which are quite easy to implement are bubble sort and insertion sort. With the second one being more efficient in practice (even though both are O(n2)).

And about your question style, it is a well-written first question.

PS: If you don't know what O(n) means, check this.

EDIT As why the current approach doesn't work, observe that the inner loop always finds the minimum of the whole array, thus it always return the same result.

Here is an idea if you want to change your code as little as possible, provided that the arrival times are all distinct (i.e., not two flights with same arrival time. That might be the inherent meaning of single airport in the assignment): Just store the previously found minimum arrival time and only assign j to minIdex if the arrival time of jth item is not equal to the stored minimum. Variable definition aside, it only adds one line to your code. I save the implementation as an exercise.

Another approach, for arrays with non distinct values it to remove the found minimum from the array, or set its value to a maximum. This though changes the content of the array, thus you need to make a copy of it first.

Answer 2

minIndex will always be the same, so pointerArray[i] will get same value - the address of minIndex element of flightArray. You're not sorting, you're simply looking for minimum element

Answer 3

Bubblesort is easy enough to implement even if it is not the most performant:

• Fill the array with all the pointers.
• loop until all sorted
  • loop from first element and swap with next if their order is wrong until the sorted elements are reached (at that point the end element is highest, thus sorted)

Remark that for all other than educational purposes (or possible optimization), std::sort should be preferred over own implementations.

A comment stated that bubblesort is complex and difficult, so I added an implementation of the algorithm in my answer. Mind you that especially the end-condition of the inner loop (j < i - 1) must be correct and that the direction of the outer and inner loop must be opposite. And it can be optimised by stopping if no swap was done, but we weren't concerned with performance in the first place.

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]);
    }
  }
}

Answer 4

First: was the idea that you write your own sort function, or that you show the initiative of looking it up, and using the std::sort? (If it's a good course, I'd expect the latter.)

If you do want to write your own, insertion sort is probably the simplest: you have a simple invariant: the array below i is already sorted, so you just have to find the position to insert the element i in it (pushing any following elements up one), and the array below i + 1 is now sorted. Start with i == 0 (since the array below 0 is empty, it is by definition sorted), and work up until you've covered every element.

Answer 5

I would suggest learning how to use STL algorithms. They have very good performance and can be composed together to do almost any task.

Here is a sample that should integrate into your exiting data structure.

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

Here is an example of its usage in some test code.

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

Here is the output

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