Course Project: Parallel Sorting of an Intransitive Ordered Set

Project Proposal: Sorting of Transitive Total Ordered Sets is one of the most researched topics in Computer Science. A generalization of this is sorting an Intransitive Total Ordered Set which is, therefore, more complex. While for a Transitive Total Ordered Set (e. g. a subset of the real numbers) holds a >= b and b >= c implies a >= c, this does not have to be true for a Intransitive Total Ordered Set. Only a > b xor b > a is claimed. Nevertheless, it can be proven that there is always an ordering that satisfies a1 >= a2 >= a3 >= ... >= an. A good example for such a set is a tournament. Each competitor either wins or loses against every other competitor. But even if it is known that Player A defeats Player B who defeats Player C in turn, nothing can be said about the result of the match Player A versus Player C.

One of the papers listed below proposes an algorithm for sorting such a set on a EREW PRAM in parallel. I implemented this algorithm for a shared memory system using pthread and to compare it to the best known sequential algorithm, as well as to ordinary sorting algorithms.

Startup Papers: Jie Wu: On Sorting an Intransitive Total Ordered Set Using Semi-Heap
Jie Wu, Stephen Olariu: On Cost-Optimal Merge of two Intransitive Sorted Sequences

Slide Presentation (PowerPoint File) incl. Question Sheet and Demo Program (for Windows, .NET Runtime required)
Final Paper (PDF) and C-Source-Code of the implementation.

430415 visits since 1999-10-27; Last update 2017-01-12