How to sort an array struct objects representing time schedules

Question

Hello i have an array of struct objects represent time schedules.i need to sort them in an order such that the first most element after sort is closest past to current day.

The struct looks like this:

struct ScheduleItem {
   int index;
   int hh;
   int mm;
   int dow;
   long reg_timestamp;
};

index => arbitrary index number hh => hour (24) mm => minute dow => day of week (starting sunday = 0) reg_timestamp => epoch time when the schedule was created

Following are the sample schedules stored in an array of schedules called user_schedules.

index:HH:MM:DOW:EPOCH

1:20:30:0:1550951769
2:03:15:0:1550951769
2:20:30:1:1550951769
3:03:15:1:1550951769
3:20:30:2:1550951769
4:03:15:2:1550951769
4:20:30:3:1550951769
5:03:15:3:1550951769
6:03:15:4:1550951769

Assume today is 2:00 am Saturday (dow = 6)

How to use qsort to sort it such that the array is sorted in an order with first most element being closest past to current date. I just know of sorting ascending or descending so not able to get what want.

This is what i tried:

qsort((void *) &applicable_schedules, counter, sizeof(struct ScheduleItem), (compfn)nearestPast );      
candidate = applicable_schedules[0];

/**
 * Compare to sort nearest past schedule
 */
int nearestPast(struct ScheduleItem *elem1, struct ScheduleItem *elem2)
{
  if ( elem1->reg_timestamp == elem2->reg_timestamp)
  {
    return abs(elem1->dow - elem2->dow);    
  }
  else
  {
    return elem1->reg_timestamp - elem2->reg_timestamp;
  }
}

and i got 20:30:0:1550951769, which is Sunday (incorrect of-course)

I am not a c guy so have issue understanding sorting in this case.

This code is for arduino

UPDATE

For more clarification closest past should be by day of week as well as HH:MM

Are you using C or C++? The C++ way to do it is described here: https://stackoverflow.com/questions/1380463/sorting-a-vector-of-custom-objects — NathanOliver, Mar 01 '19 at 22:33
Your requirements involve the current date. Your comparison function makes no use of the current date. So it's not surprising it doesn't work. If you insist on `qsort` (instead of C++ `std::sort`), then you'll need to put the current date in a global variable and then make use of it in your comparison function. — john, Mar 01 '19 at 22:36
One alternative way of doing this would be to sort the array into normal ascending order. Then find the first date in the array that is 'closest past' the current date and then *rotate* the array so that element is in first place. E.g suppose you sort the array and you end up with 1,2,3,4,5. Suppose the current date is 2.5, so 3 is the closest past the current date. Now rotate the array so 3 ends up first, i.e. you end up with 3,4,5,1,2. — john, Mar 01 '19 at 22:40
i updated the question. I want c based code since i run it on Arduino IDE.@NathanOliver — Rajdeep Rath, Mar 01 '19 at 22:56
@john this is for Arduino. Also can you please provide some code / example type stuff. Sorry but am a bit slow to c as far as sorting goes. — Rajdeep Rath, Mar 01 '19 at 22:59
@RadeepRath I've afraid I didn't follow your requirements in sufficient detail to write some code. I hope I've given a couple of ideas for you to make some progress. — john, Mar 01 '19 at 23:07

David C. Rankin · Accepted Answer · 2019-03-02T01:00:43.610

If reg_timestamp is simply the time in seconds since epoch and you want to sort the entries in descending order, all you need do is:

int compare_sched_item_time (const void *a, const void *b)
{
    /* cast pointers to adjacent elements to struct ScheduleItem* */
    struct ScheduleItem *x = a, *y = b;

    /* (x->time < y->time) - (x->time > y->time) - descending sort
     * comparison avoids potential overflow
     */
    return (x->reg_timestamp < y->reg_timestamp) - 
           (x->reg_timestamp > y->reg_timestamp);
}

Note: the difference of the conditional expressions avoids the potential for overflow. You can use it with any numeric type. The forms are:

/* (a > b) - (a < b) - ascending sort */

and

/* (a < b) - (a > b) - descending sort */

Simply think through the cases. For ascending if (a > b) is true (e.g. 1) and (a < b) is false (e.g. 0), your conditional is 1 - 0 = 1 so b sorts before a. If they are equal, the result is 0 (no swapping needed). If (a > b) is false and (a < b) true, then the result is -1 so a sorts before b -- just like the results of strcmp, etc..

Edit - Comparison if reg_timestamp Values Equal

If you have more than one condition you wish to sort on, just test in the order of decreasing importance, e.g.

int compare_sched_item_time (const void *a, const void *b)
{
    /* cast pointers to adjacent elements to struct ScheduleItem* */
    struct ScheduleItem *x = a, *y = b;

    /* (x->time < y->time) - (x->time > y->time) - descending sort
     * comparison avoids potential overflow
     */
    if (x->reg_timestamp != y->reg_timestamp)
        return (x->reg_timestamp < y->reg_timestamp) - 
               (x->reg_timestamp > y->reg_timestamp);
    /* compare dow next */
    else if (x->dow != y->dow)
        return (x->dow < y->dow) - (x->dow > y->dow);
    /* compare hh next */
    else if (x->hh != y->hh)
        return (x->hh < y->hh) - (x->hh > y->hh);
    /* finally compare mm */
    else
        return (x->mm < y->mm) - (x->mm > y->mm);
}

That is the benefit of qsort. You can make any element sort any way you wish just be returning -1, 0, 1 for your desired condition.

reg_timestamp is not the schedule time. its creation time. it is possible that u create a a schedule for 3 days at same time. schedule then represented by individual ScheduleItems as i have mentioned. Additional things that is needed 1. if reg_timestamp are same sort by nearest past dow 2. if dow are same sort by HH MM Also see the example i have : Multiple schedules have same `reg_timestamp` — Rajdeep Rath, Mar 02 '19 at 00:20
OK, you need to do no more than add additional copies of the same check. Whatever you want as your primary check, check that first and return the results if your comparison is satisfied. If not, drop down to the next comparison of `DOW`, repeat. Let me know if you hare having problems with that logic. It is the same comparison and you have already cast to `struct ScheduleItem`, so just compare `x-dow`, etc.. — David C. Rankin, Mar 02 '19 at 00:53
Thank you very much `David C. Rankin`. i was getting lost trying : `return (((dtnow.DayOfWeek()- elem1->dow) < (dtnow.DayOfWeek()-elem2->dow)) - ((dtnow.DayOfWeek()- elem1->dow) > (dtnow.DayOfWeek()-elem2->dow)));` i will try your approach and follow your advice and get back if i still have issues. Thank you very much for your time.! — Rajdeep Rath, Mar 02 '19 at 13:29
Remember, the conditionals are to avoid overflow. You can just return `a - b`, but if `a` is a large negative and `b` is large positive, you can overflow your type easily. The `(a < b) - (a > b)` guarantees the comparison will not overflow. — David C. Rankin, Mar 03 '19 at 00:56

How to sort an array struct objects representing time schedules

1 Answers1