Sorting algorithm for a non-comparison based sort problem?

Asked 2008-11-17T21:38:08.190

I am currently faced with a difficult sorting problem. I have a collection of events that need to be sorted against each other (a comparison sort) and against their relative position in the list.

In the simplest terms I have list of events that each have a priority (integer), a duration (seconds), and an earliest occurrence time that the event can appear in the list. I need to sort the events based on priority, but no event can appear in the list before its earliest occurrence time. Here's an example to (hopefully) make it clearer:

// Psuedo C# code
class Event { int priority; double duration; double earliestTime ; }

void Example()
{
    Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 };
    Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 };
    Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 };
    Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 };

    // assume list starts at 0.0 seconds
    List<Event> results = Sort( new List<Event> { a, b, c, d } );

    assert( results[ 0 ] == a ); // 4.0 seconds elapsed
    assert( results[ 1 ] == c ); // 7.0 seconds elapsed
    assert( results[ 2 ] == b ); // 12.0 seconds elapsed
    assert( results[ 3 ] == d ); // 14.0 seconds elapsed
}

Item "b" has to come last because it isn't allowed to start until 6.0 seconds into the list, so it is deferred and "c" gets to go before "b" even though its priority is lower. (Hopefully the above explains my problem, if not let me know and I'll edit it.)

My current idea is to use an insertion sort to manage the sorting process. Unlike many of the other common sorting algorithms, insertion sort decides the order of the list one at a time and in order. So for each index

Edit Report

3 Answers

This is actually more than a sorting problem. It's a single-machine scheduling problem with release dates. Depending on what you are trying to do, the problem might be NP-Hard. For example, if you are trying to mimimize the weighted-sum of the completion times (the weight being inversely proportional to the priority), the the problem is categorized as

1|ri;pmtn|Σ wiCi

and is NP-hard. There are numerous papers on this topic, but it might be more than what you need.

In your case, you never want a solution with gaps, so what you might just need to do is a simple discrete-event simulation ( O(n log(n)) ) time. You need to store released_jobs as a priority queue.

unreleased_jobs = jobs  // sorted list of jobs, by release date
released_jobs = {}      // priority queue of jobs, by priority
scheduled_jobs = {}     // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {

    while (unreleased_jobs.top().earliestTime  <= t) {
        released_jobs.push(unreleased_jobs.pop())
    }
    if (!released_jobs.empty()) {
       next_job = released_jobs.pop();
       scheduled_jobs.push_back(next_job)
       t = t + next_job.duration
    } else {
       // we have a gap
       t = unreleased_jobs.top().earliestTime
    }
}

One problem is that you might have a low-priority job with a release time just before a short, high-priority job, but it will produce a schedule with the property that there are no gaps (if a schedule with no gaps is possible).

answered 2008-11-17T21:49:16.433

I think you should sort the list twice: first by priority and then by earliest time, using any stable sort algorithm, for instance insertion sort. That way the time will be increasing and for each time things will be sorted by priority.

Unless you see something I don't you can completely ignore the duration of each event for the purpose of the sort.

http://en.wikipedia.org/wiki/Category:Stable_sorts

answered 2008-11-17T21:43:39.457

I'm not entirely certain I understand the intricacies of your problem, but my instinct tells me you need to define a relationship between priority and start time. The example would be:

Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };

So, do we go ahead and start b at time = 0, or do we wait for a tick and then start a because it's higher priority? Suppose there were more events with more priorities and longer time tradeoffs. I think you need a rule along the lines of "if the next event is X higher priority and the gap (between now and the earliest time) is less than Y seconds, wait and then start the higher priority event. otherwise start the low priority event (thus pushing back the high priority one)".

answered 2008-11-17T22:40:20.387

Sorting algorithm for a non-comparison based sort problem?

3 Answers

Your Answer