Sorting dates (DD/MM/YYYY) with insertion sort [closed]

Question

I'm having troubles with a coding problem. Yes, I need to write a C++ program which sorts dates. I've tried several methods. Using 2D arrays and now parallel arrays.

The problem I have with my parallel array to keeping tract of those which haven't been sorted yet. That is the YYYY has been sorted. I need to keep track of the MM. Then DD.

Please make some suggestions as to how I should approach this. Or did I approach this question entirely in the wrong way?

#include <iostream>
#include <string>

using namespace std;

/*
Write a program in C++ to ask the user to enter dates in dd/mm/yyyy format.
The number of dates that the user can enter should also be specified by the user.
Sort the dates in ascending order using an appropriate sorting algorithm.
Also write a small description as to why you have chosen this particular sorting technique.

Example output screen:

Enter no of dates to enter: 5

Enter the first date: 12/05/1945
Enter the second date: 01/01/2001
Enter the third date: 05/12/1999
Enter the fourth date: 11/03/1972
Enter the fifth date: 15/12/1999

After sorting the dates are:

12/05/1945
11/03/1972
05/12/1999
15/12/1999
01/01/2001

*/



string ConvertToWord(unsigned int input) {
    string output = "";
    int ones_place = input % 10;
    int tens_place = (input - ones_place) % 100;

    if (input >= 10 && input < 20) {
        switch (ones_place) {
        case 0:
            output += "Tenth";
            break;
        case 1:
            output += "Eleventh";
            break;
        case 2:
            output += "Twelfth";
            break;
        case 3:
            output += "Thirteenth";
            break;
        case 4:
            output += "Fourteenth";
            break;
        case 5:
            output += "Fiftheenth";
            break;
        case 6:
            output += "Sixteenth";
            break;
        case 7:
            output += "Seventeeth";
            break;
        case 8:
            output += "Eighteeth";
            break;
        case 9:
            output += "Nineteeth";
            break;
        }
    }

    else if ((input >= 20 && input < 99) || (input > 0 && input < 20)) {
        switch (tens_place) {
            case 20:
                output += "Twenty";
                break;
            case 30:
                output += "Thirty";
                break;
            case 40:
                output += "Forty";
                break;
            case 50:
                output += "Fifty";
                break;
            case 60:
                output += "Sixty";
                break;
            case 70:
                output += "Seventy";
                break;
            case 80:
                output += "Eighty";
                break;
            case 90:
                output += "Ninety";
                break;
        }
        if (tens_place > 0 && ones_place > 0) {
            output += "-";
        }
        switch (ones_place) {
        case 1:
            output += "First";
            break;
        case 2:
            output += "Second";
            break;
        case 3:
            output += "Third";
            break;
        case 4:
            output += "Fourth";
            break;
        case 5:
            output += "Fifth";
            break;
        case 6:
            output += "Sixth";
            break;
        case 7:
            output += "Seventh";
            break;
        case 8:
            output += "Eighth";
            break;
        case 9:
            output += "Nineth";
            break;
        case 10:
            output += "Twentth";
            break;
        }
    }

    return output;
}

int* ToArray(string word) {

    word += "/";
    int* result = new int[3];
    string current_word = "";
    int num_words = 0;
    for (int i = 0; i < word.length(); i++) {
        char c = word.at(i);
        if (c != '/') {
            current_word += c;
        }
        else {
            result[num_words] = stoi(current_word);
            current_word = "";
            num_words++;
        }
    }

    return result;
}

void ToArrays(int* days, int* months, int* years, int index, string input) {
    input += "/";
    string current_input = "";
    int num_input = 0;
    for (int i = 0; i < input.length(); i++) {
        char c = input.at(i);
        if (c != '/') {
            current_input += c;
        }
        else {
            if (num_input == 0) {
                days[index-1] = stoi(current_input);
            }
            else if (num_input == 1) {
                months[index-1] = stoi(current_input);
            }
            else if (num_input == 2) {
                years[index-1] = stoi(current_input);
            }
            current_input = "";
            num_input++;
        }
    }

}

int** AddDatesInto2DArray(int** result, int _num_dates, string word, int index) {

    int* sorted_date = ToArray(word);

    for (int i = 0; i < 3; i++) {
        result[index-1][i] = sorted_date[i];
    }

    return result;
}


void InsertionSort(int* array, int length) {
    int j, temp;
    for (int i = 1; i < length; i++) {
        j = i;
        while (j > 0 && array[j] < array[j - 1]) {
            temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
            j--;
        }
    }

}

void InsertionSort(int* sorting, int* a, int* b, int length) {
    bool all_sorted = true;

    int* unsorted_index = new int[length];
    int* unsorted_sorting = new int[length];
    int* unsorted_a = new int[length];
    int* unsorted_b = new int[length];

    int j, temp, temp_a, temp_b;
    for (int i = 1; i < length; i++) {
        j = i;

        if (sorting[i] == sorting[j-1]) {

        }

        while (j > 0 && sorting[j] < sorting[j - 1]) {
            temp_a = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp_a;

            temp_b = b[j];
            b[j] = b[j - 1];
            b[j - 1] = temp_b;

            temp = sorting[j];
            sorting[j] = sorting[j - 1];
            sorting[j - 1] = temp;
            j--;
        }
    }
}

int main() {

    cout << "Enter the number of dates to enter [Three Digit] : ";
    int num_dates = 0;
    cin >> num_dates;

    int* int_days = new int[num_dates];
    int* int_months = new int[num_dates];
    int* int_years = new int[num_dates];


    for (int i = 1; i < num_dates+1; i++) {
        string num_word = ConvertToWord(i);
        cout << endl;
        cout << "Enter the " << num_word << " date : ";
        string date_input = "";
        cin >> date_input;
        ToArrays(int_days, int_months, int_years, i, date_input);
    }

    InsertionSort(int_years, int_days, int_months, num_dates);

    for (int i = 0; i < num_dates; i++) {
        cout << int_days[i] << "/" << int_months[i] << "/" << int_years[i] << endl;
    }




    int i_temp = 0;
    cin >> i_temp;

    return (0);
}

Answer 1

Here are some ideas and suggestions for improving your code.

First of all it's best to combine all information about the dates in a stuckt (as also suggested by Mat) instead of having three-four separate arrays. For example:

struct Date{
   int year, month, day, date_int;

   Date(std::string date) : year(date_to_year(date)),  month(date_to_month(date)), 
             day(date_to_day(date)), date_int(date_to_int(day, month, year)) {}
}

The date_int integer is added for convenience when doing the sorting (see below) and I have also added a contructor to initialize the date from a string. The functions to extract year, month and day are quite simple if you use built-in string manipulations like for example std::string::substr (to extract a substring) and std::atoi (to convert a string to an int):

inline int date_to_year(std::string date){
  return std::atoi(date.substr(6,4).c_str());
}

inline int date_to_month(std::string date){
  return std::atoi(date.substr(3,2).c_str());
}

inline int date_to_day(std::string date){
  return std::atoi(date.substr(0,2).c_str());
}

I would also use some standard container, like std::vector, to store the dates. Example use:

// Make the container
std::vector<Date> dates;

// Make a new date and add it to the container
std::sting date = "11/05/2001"
Date newdate(date);
dates.push_back(newdate);

One advantage of this is that vector takes care of memory allocation and deallocation for you so you don't have to think about this aspect. Also if you want to remove one date from the list you don't have to go through all three arrays you can simply use dates.erase (dates.begin()+i-1) to delete the i'th date in the container.

When reading in dates I would also check if the date is a viable date and if not then ask the user to enter a new date. Some useful checks to perform: is the year/day/month a positive integer?, is day<32?, is month < 13? and so on. If you want to be really thorough then you should also add checks about Feb. 29.

To sort the dates I would use a library instead of writing this yourself (unless that is the point of the exercise). For example std::sort can be used for this. Instead of comparing year, month and day at the same time you can map the date uniquely to an integer using for example:

inline int date_to_int(int day, int month, int year){
  return year*10000 + month*100 + day;
}

If you have date_int in your Date struct then you can sort the dates very simply:

// Comparison function for two dates based on date_int
inline bool compare_dates(const Date &a, const Date &b){
  return a.date_int > b.date_int;
}

// Sort dates using compare_dates as the comparison function
std::sort(dates.begin(), dates.end(), compare_dates);

If you have to implement the sorting function yourself then you can still use a comparison based on date_int to avoid having to compare year, month and day seperately.

Answer 2

Major critiques:

1. There is no need for your ConvertToWord function. The problem statement does not say to do that. Your ConvertToWord is gold-plating. (Aside: Your implementation has flaws.) Replace that 100 line long function with a simple std::cout << "Enter date number " << idate << ": ";

   Edit: On second thought, the problem statement does imply that something along the lines of ConvertToWord is needed. However, a good programmer will push back on stupid requirements. This is a stupid requirement.

2. There is no need for your two InsertionSort functions. Those two functions represent another big chunk of code, and they use insertion sort. Your first choice for a sort function should almost always be std::sort. Unless you have very weird data, std::sort will be much faster than a hand-rolled sorting function. Even if you do have very weird data to be sorted, your first thought should be std::sort with a custom comparison function.

3. There is no need for your ToArray, ToArrays, and AddDatesInto2DArray, either. You chose a poor representation. Sorting dates represented in the form DD/MM/YYYY is hard. On the other hand, sorting dates represented as a string of the form YYYYMMDD or an integer whose decimal representation is YYYYMMDD is trivial. Just use std::sort and you will get the correct sort order. Internally, you should have represented your data in some sort of YYYYMMDD format. Assuming properly formatted user input, converting from a string of the form DD/MM/YYYY to a string of the form YYYYMMDD is a one liner. Converting back to a string of the form DD/MM/YYYY is another one liner. This of course assumes perfectly formatted user input; a professional program would care very much about malformed user input. But the problem statement doesn't ask you to check for that. Those checks would be another form of gold plating here.

4. This is C++. In general, one should prefer one of the standard containers over C-style arrays. (This is not the case when doing numerical or scientific programming. But that's not what you are doing here.) In this case, a std::vector<std::string> or std::vector<int> would be just right.

Lesser critiques:

1. Regarding using namespace std; -- Don't use that. In a professional code review, that is a sign of a rank beginner who has read the wrong books.

2. The standard idiom for an indexed loop in C++ is for (i = 0; i < limit; ++i) (in C the increment is written as i++ instead of ++i.) Anytime I see a indexed loop that is not in that form in a code review, I have to wonder why the author did that.

Instead of hundreds of lines of code,

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

    int main ()
    {
        std::cout << "Enter the number of dates to enter : ";
        unsigned int num_dates;
        std::cin >> num_dates;

        std::vector<std::string> dates;
        for (unsigned int ii = 0; ii < num_dates; ++ii)
        {
            std::cout << "Enter date number " << ii+1 << ": ";
            std::string date;
            std::cin >> date;
            dates.push_back(date.substr(6) + date.substr(3,2) + date.substr(0,2));
        }

        // Sort the array.
        // Why this way? std::sort is always the first choice.
        std::sort (dates.begin(), dates.end());

        std::cout << "Sorted dates:\n";
        for (auto& date : dates)
        {
            std::cout << date.substr(6,2) + '/' +
                         date.substr(4,2) + '/' +
                         date.substr(0,4) + '\n';
        }
    }