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

Question 1

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

Question 2

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.

Question 3

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

Question 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.

Question 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