Given an array arr[] of N dates in the form of “dd-mm-yyyy”, the task is to sort these dates in ascending order.
Examples:
Input: arr[] = { "25-08-1996", "03-08-1970", "09-04-1994" } Output: 03-08-1970 09-04-1994 25-08-1996 Input: arr[] = { "14-02-1972", "01-01-2001"} Output: 14-02-1972 01-01-2001
A simple solution that comes to our mind is to delete all ‘-‘ from array and then sort array in ascending o order, but simply sorting doesn’t work.
For example, 09-04-2020 is greater than 19-04-2019, but in output 09-04-2020 comes before 19-04-2019.
So how do we go about it?
The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort dates. Given two dates date1 and date2, how should myCompare() decide which date to put first –
- We compare two years year1 (date1.substr(6, 4)) and year2 (date2.substr(6, 4)). If year1 is smaller, then date1 should come before date2 in output, else date2 should come before.
- Else we compare two months month1 (date1.substr(3, 2)) and month2 (date2.substr(3, 2)). If month1 is smaller, then date1 should come before date2 in output, else date2 should come before.
- Else we compare two days day1 (date1.substr(0, 2)) and day2 (date2.substr(0, 2)). If day1 is smaller, then date1 should come before date2 in output, else date2 should come before.
Following is the implementation of the above approach.
To keep the code simple, dates are considered as strings in the form “dd-mm-yyyy”, the vector is used instead of a normal array.
Below is the implementation of the above approach:
// Given an array of dates, program to arrange the dates in // ascending order #include <bits/stdc++.h> using namespace std; // A comparison function which is used by sort() in printDatesAscending() bool myCompare(string date1, string date2) { string day1 = date1.substr(0, 2); string month1 = date1.substr(3, 2); string year1 = date1.substr(6, 4); string day2 = date2.substr(0, 2); string month2 = date2.substr(3, 2); string year2 = date2.substr(6, 4); if (year1 < year2) return true; if (year1 > year2) return false; if (month1 < month2) return true; if (month1 > month2) return false; return day1 < day2; } // function that prints the dates in ascending order void printDatesAscending(vector<string> arr) { // Sort the dates using library sort function. The function uses // our comparison function myCompare() to compare two strings. sort(arr.begin(), arr.end(), myCompare); for (int i = 0; i < arr.size(); i++) cout << arr[i] << "\n"; } // Driver program to test above functions int main() { vector<string> arr; arr.push_back("30-06-1989"); arr.push_back("03-09-1971"); arr.push_back("15-07-1994"); arr.push_back("19-07-1998"); arr.push_back("15-01-1971"); printDatesAscending(arr); return 0; }
Output:
15-01-1971 03-09-1971 30-06-1989 15-07-1994 19-07-1998
Time Complexity: O(n logn)
Space Complexity: O(n)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.