Skip to content

Instantly share code, notes, and snippets.

@fatihsokmen
Created February 16, 2015 11:08
Show Gist options
  • Save fatihsokmen/b63350cf701eed44d004 to your computer and use it in GitHub Desktop.
Save fatihsokmen/b63350cf701eed44d004 to your computer and use it in GitHub Desktop.
Finding kth smallest element of array
public static int quickSelect(int[] a, int k) {
int pivot = a[0];
int lenOfMinThanPivot = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] < pivot) {
lenOfMinThanPivot++;
}
}
if (lenOfMinThanPivot == k - 1) {
return pivot;
} else if (lenOfMinThanPivot < k - 1) {
int[] GREATER = new int[a.length - lenOfMinThanPivot - 1];
int gx = 0;
for (int j = 1; j < a.length; j++) {
if (a[j] >= pivot) {
GREATER[gx++] = a[j];
}
}
return quickSelect(GREATER, k - lenOfMinThanPivot - 1);
} else {
int[] LESS = new int[lenOfMinThanPivot];
int lx = 0;
for (int j = 1; j < a.length; j++) {
if (a[j] < pivot) {
LESS[lx++] = a[j];
}
}
return quickSelect(LESS, k);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment