👀 Views: 50 💬 Answers: 1 📅 Created: 2025-06-08

java algorithm quickselect Java

I'm learning this framework and I tried several approaches but none seem to work... I'm trying to implement the Quickselect algorithm in Java to find the kth smallest element in an array, but I'm consistently getting incorrect results for certain values of k. My implementation seems to work fine for smaller arrays, but fails when the array size increases. Here's the code I have: ```java public class QuickSelect { public static int quickSelect(int[] arr, int left, int right, int k) { if (left == right) return arr[left]; // If the list contains only one element int pivotIndex = partition(arr, left, right); if (k == pivotIndex) { return arr[k]; } else if (k < pivotIndex) { return quickSelect(arr, left, pivotIndex - 1, k); } else { return quickSelect(arr, pivotIndex + 1, right, k); } } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; // Choose the rightmost element as pivot int i = left; for (int j = left; j < right; j++) { if (arr[j] < pivot) { swap(arr, i, j); i++; } } swap(arr, i, right); return i; } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ``` When I call `quickSelect(new int[]{3, 6, 2, 7, 5, 1}, 0, 5, 2)`, I expect to get `3` as the output (the 3rd smallest element), but I'm getting `5` instead. I believe my partition logic is flawed when the array contains duplicate values or when the pivot is not properly chosen. I've tried using different pivot selection strategies, like choosing a random pivot or the median, but the question continues. Is there something I'm missing here? Could it be an off-by-one behavior in how I'm calculating the pivotIndex or k? Any insights or improvements to my implementation would be greatly appreciated! I'm working on a API that needs to handle this. I'd really appreciate any guidance on this. Am I missing something obvious? The project is a REST API built with Java.