Pourriez-vous expliquer le principe de fonctionnement de l'algorithme Quickselect?

L'algorithme Quickselect est utilisé pour trouver le k-ième élément dans un tableau non trié. Il est basé sur l'idée du tri rapide (Quicksort), mais au lieu de trier complètement le tableau, il sélectionne récursivement uniquement la partie où l'élément recherché peut se trouver.

Principe de fonctionnement:

1. Choisir un élément pivot.
2. Diviser le tableau en éléments inférieurs et supérieurs au pivot.
3. Déterminer la position du pivot après la partition.
4. Si la position correspond à k, retourner le pivot.
5. Sinon, rechercher récursivement dans la partie gauche ou droite du tableau.

Cela permet de trouver le k-ième élément en moyenne en temps O(n).

Exemple en Java:

public int quickselect(int[] arr, int k) {
    return quickselectHelper(arr, 0, arr.length - 1, k);
}

private int quickselectHelper(int[] arr, int left, int right, int k) {
    if (left == right) return arr[left];
    int pivotIndex = partition(arr, left, right);
    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickselectHelper(arr, left, pivotIndex - 1, k);
    } else {
        return quickselectHelper(arr, pivotIndex + 1, right, k);
    }
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int temp = arr[i];
    arr[i] = arr[right];
    arr[right] = temp;
    return i;
}