Academic Journals Database
Disseminating quality controlled scientific knowledge

Robustness versus Performance in Sorting and Tournament Algorithms

ADD TO MY LIST
 
Author(s): Wilfried Elmenreich | Tobias Ibounig | István Fehérvári

Journal: Acta Polytechnica Hungarica
ISSN 1785-8860

Volume: 6;
Issue: 5;
Start page: 7;
Date: 2009;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: sorting algorithms | robustness | tournaments | iterated knockout system

ABSTRACT
In this paper we analyze the robustness of sorting and tournament algorithmsagainst faulty comparisons. Sorting algorithms are differently affected by faultycomparisons depending on how comparison errors can affect the overall result. In general,there exists a tradeoff between the number of comparisons and the accuracy of the result,but some algorithms like Merge Sort are Pareto-dominant over others. For applications,where the accuracy of the top rankings is of higher importance than the lower rankings,tournament algorithms such as the Swiss System are an option. Additionally, we propose anew tournament algorithm named Iterated Knockout Systems which is less exact but moreefficient than the Swiss Systems.
RPA Switzerland

RPA Switzerland

Robotic process automation

    

Tango Jona
Tangokurs Rapperswil-Jona