Meg tudná magyarázni a Quickselect algoritmus működési elvét?

A Quickselect algoritmusát arra használják, hogy megtalálják a nem rendezett tömb k-adik legnagyobb elemét. A gyorsrendezés (Quicksort) ötletén alapul, de ahelyett, hogy az egész tömböt rendezné, csak azt a részt választja ki rekurzívan, ahol a keresett elem lehet.

Működési elv:

1. Egy pivot elemet választanak.
2. A tömböt kisebb és nagyobb elemekre osztják a pivottól.
3. Meghatározzák a pivot pozícióját a partíció után.
4. Ha a pozíció megegyezik k-val, visszaadják a pivotot.
5. Ellenkező esetben rekurzívan keresnek a bal vagy jobb részben.

Ez lehetővé teszi, hogy átlagosan O(n) idő alatt megtaláljuk a k-adik elemet.

Java példával:

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;
}