CODEWITHSUNDEEP
algorithmlanguage-agnosticsortingtopological-sortpartial-ordering
mike g
mike g

Reputation: 1801

What is the best way to sort a partially ordered list?

Probably best illustrated with a small example.
Given the relations

A < B < C
A < P < Q

Correct outputs would be

ABCPQ or APQBC or APBCQ ... etc.

In other words, any ordering is valid in which the given relationships hold.

I am most interested in the solution that is easiest to implement, but the best O(n) in speed and time is interesting as well.

Upvotes: 9

Views: 3505

Answers (3)

Tanveer Badar
Tanveer Badar

Reputation: 5512

You could repeatedly call make_heap, pop_heap in C++ with the sequence at hand.

Upvotes: 1

starblue
starblue

Reputation: 56802

This is called topological sorting.

The standard algorithm is to output a minimal element, then remove it and repeat until done.

Upvotes: 13

user54579
user54579

Reputation: 4688

Do several sorts. First sort according to the first rule, then according to the second one and so on. Should work, unless your rules contain contradictions. sure easy enough to implement.

Upvotes: 1

Related Questions