StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSorting algorithm for a non-comparison based sort problem?
primarykey
Id
297035
data
AcceptedAnswerId
297079
AnswerCount
10
ClosedDate
CommentCount
3
CommunityOwnedDate
CreationDate
2008-11-17T21:38:08.190
FavoriteCount
7
LastActivityDate
2016-10-19T21:05:29.390
LastEditDate
2016-10-19T21:05:29.390
LastEditorUserId
14167
OwnerUserId
11889
ParentId
0
PostTypeId
1
Score
16
ViewCount
2035
LastEditorDisplayName
ARKBAN
text
Body
I am currently faced with a difficult sorting problem. I have a collection of events that need to be sorted against each other (a <a href="http://en.wikipedia.org/wiki/Comparison_sort" rel="nofollow noreferrer">comparison sort</a>) 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: <pre><code>// 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 } </code></pre> 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 <a href="http://en.wikipedia.org/wiki/Insertion_sort" rel="nofollow noreferrer">insertion sort</a> 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 I should be able to find the next lowest priority event whose earliest occurrence time will be satisfied. I'm hoping to find resources about sorting algorithms and data structures to help me design a good solution for this "sort" of problem. My real problem is actually more complex than this: hierarchical sorting, variable buffers between events, multiple non-constant time constraints, so the more information or ideas the better. Speed and space are not really a concern. Accuracy in sorting and maintainability of the code are a concern. Edit: Clarifications (based on comments) <ul> <li>Events consume their entire duration (that is there is no overlap of events allowed)</li> <li>Events must occur at or after their earliestTime, they cannot occur before their earliestTime.</li> <li>Events can occur later than their earliestTime if lower priority events exist</li> <li>Events cannot be interrupted</li> <li>There is a maximum duration the sum of all events that can fit in a list. This is not shown above. (In reality the duration of all events will be far greater than the time list's maximum duration.)</li> <li>There cannot be any gaps. (There are no holes to try and back fill.)</li> </ul> Edit: Answer While David Nehme gave the answer I selected, I wanted to point out that his answer is an insertion sorts at heart, and several other people provided insertions sort type answers. This confirms for me that a specialized insertion sort is probably the way to go. Thanks to all of you for your answers.
Tags
<c#><algorithm><sorting><comparison><mathematical-optimization>
Title
Sorting algorithm for a non-comparison based sort problem?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USDavid Nehme
UserOwnerUserId
1. USARKBAN
plurals
PostLinksPostIdRelatedPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POSorting algorithm for a non-comparison based sort problem?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POSorting algorithm for a non-comparison based sort problem?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 POSorting algorithm for a non-comparison based sort problem?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.