• information retrieval
• selection
• sorting
• tournament graphs

Sorting and selection are two fundamental problems in theoretical computer science, their optimal solution in the usual comparison model is a typical introductory topic of textbooks in algorithmics. Suppose that, instead of the usual comparison operation, we dispose of a black-box comparison function, that sometimes can err, producing inconsistent outputs. Studying selection and sorting in this setting becomes more interesting: we need to both set up models describing how our comparator may fail, and design algorithms to efficiently perform approximate selection and sorting. In this thesis we will overview various models to define in which sense the comparisons are {\em faulty} and what kind of approximate sorting or selection we can perform. For every model exposed we will analyze the state-of-the-art complexity of selection and sorting in those models. The last chapter contains an original result, partially published in \ref{spire} that solves the problem of finding the maximum element in presence of faulty comparisons and employs a novel parameterization, that captures an important feature of applications.