## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du séminaire du Mardi 1 Juin 2010

*Interval Sorting*

## par Conrado Martinez (UPC, Barcelone)

In the interval sort problem, we are given an array *A* of
*n* items and *p* ranges of ranks
*I*_{1}=[*l*_{1},*u*_{1}],
...,
*I*_{p}=[*l*_{p},*u*_{p}].
The goal is to rearrange the array so that
*A*[*l _{t}*..

*u*] contains the

_{t}*l*-th, ...,

_{t}*u*-th smallest elements of

_{t}*A*in nondecreasing order, for all

*t*, 1 ≤

*t*≤

*p*, and

*A*[

*u*+1..

_{t}*l*

_{t+1}-1] contains the (

*u*+1)-th, ..., (

_{t}*l*

_{t+1}-1)-th smallest elements of

*A*, for all

*t, 0 ≤ t ≤*p. That is, the array is sorted by blocks, with sorted and unsorted blocks alternating. One of the most interesting aspects of this research is the unification of several important and related problems (sorting, selection, multiple selection, partial sorting) under a single framework. Results on interval sorting generalize the results for any of these particular---and fundamental---problems.

We propose a divide-and-conquer algorithm, owing to quicksort
and quickselect, named chunksort, to solve the problem. We give an
exact expression for the average number of comparisons made by the
basic variant of chunksort. Then we consider what is the expected
optimal number of comparisons needed to solve an interval sort
instance and we design a variant of chunksort that achieves near
optimal expected performance, up to *n*+*o*(*n*)
comparisons. In fact, we conjecture that the algorithm that we
propose has actually optimal expected performance up to
*o*(*n*) terms and provide some evidence for this
conjecture. To describe our near-optimal solution to interval
sorting, I will also discuss some of my previous work on optimal
quicksort and on optimal quickselect.

This is joint work with Rosa M. Jimenez.