Skip to content

Instantly share code, notes, and snippets.

@nichtemna
Created September 20, 2016 15:20
Show Gist options
  • Save nichtemna/3b747694316ff22618e3b115a8d570b2 to your computer and use it in GitHub Desktop.
Save nichtemna/3b747694316ff22618e3b115a8d570b2 to your computer and use it in GitHub Desktop.
Quick select algorithm searching for median in array
public class QuickSelect {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
array[i] = scanner.nextInt();
}
int pos = array.length / 2;
int median = quickSelect(array, pos, 0, array.length - 1);
System.out.print(median);
}
private static int quickSelect(int[] array, int pos, int left, int right) {
if (left == right && left == pos) {
return array[left];
}
int posRes = partition(array, left, right, pos);
if (posRes == pos) {
return array[posRes];
} else if (posRes < pos) {
return quickSelect(array, pos, posRes + 1, right);
} else {
return quickSelect(array, pos, left, posRes - 1);
}
}
private static int partition(int[] array, int left, int right, int pos) {
int pivot = array[left];
int position = left;
for (int i = left + 1; i <= right; i++) {
if (array[i] <= pivot) {
position++;
swap(array, i, position);
}
}
swap(array, left, position);
return position;
}
private static void swap(int[] array, int first, int second) {
int temp = array[first];
array[first] = array[second];
array[second] = temp;
}
}
@suisuiwudi
Copy link

How about length of the array is even?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment