Μπορείτε να εξηγήσετε την αρχή λειτουργίας του αλγορίθμου Quickselect;

Ο αλγόριθμος Quickselect χρησιμοποιείται για την εύρεση του k-ου μεγαλύτερου στοιχείου σε έναν μη ταξινομημένο πίνακα. Βασίζεται στην ιδέα της γρήγορης ταξινόμησης (Quicksort), αλλά αντί να ταξινομήσει πλήρως τον πίνακα, επιλέγει αναδρομικά μόνο το μέρος όπου μπορεί να βρίσκεται το ζητούμενο στοιχείο.

Αρχή λειτουργίας:

1. Επιλέγεται ένα στοιχείο πυρήνα (pivot).
2. Ο πίνακας διαιρείται σε στοιχεία μικρότερα και μεγαλύτερα από το pivot.
3. Καθορίζεται η θέση του pivot μετά τη διαίρεση.
4. Αν η θέση ταιριάζει με το k, επιστρέφεται το pivot.
5. Διαφορετικά, αναζητείται αναδρομικά στο αριστερό ή δεξιό μέρος του πίνακα.

Αυτό επιτρέπει την εύρεση του k-ου στοιχείου κατά μέσο όρο σε χρόνο O(n).

Παράδειγμα σε 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;
}