Order statistics means, given as input an array A[p...q] and an integer k with p <= k <= q, we want to find the kth smallest element in the array; in other words, the element of rank k.

The algorithm has an expected running time which is linear, while the worst case is Theta(n²).

The main function in the code is randSelect. If p is equal to q, we passed an array of just one element, so it doesn't matter what rank we request, it will be always that element (of course, by the time we reach that piece of code, everything will be fine, and rank would not be outside the limits).

Otherwise, we partition the array around a random pivot (which isn't really random as you can see, but whatever) and return the pivot's index. The partition method is well explained in the quicksort page.

The variable k will contain the rank of the pivot: in fact, if every element at the pivot's left is smallest than it, so its rank is [pivot index] - p (that is, possible elements not considered "before" p) + 1 because the indexes start from 0 not 1 (there is no rank 0!).

Then, there are three choices:

1. You're lucky, because the user requested exactly the element of rank k! So all you need to do is return A[r].

2. The requested rank is smallest, so can be found only in the left subarray. The algorithm go looking for it there.

3. The rank is larger, so we need to look for it in the right subarray, but with a small change. We are sure the subarray A'[p...r] contains elements that are all smallest than the one we're going to find. So there is a range of ranks from 1 to a certain x that we're going to skip. The important thing is, when we call again the method, this information is lost! So we need to eliminate all this ranks that will be lost, and pass to the method rank-k instead of rank alone.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

import java.util.Arrays; import javax.swing.JOptionPane; public class OrderStatistics { public static void main(String[] args) { int[] array = {6, 3, 7, 8, 1, 9, 5, 4, 10, 2}; int choice; System.out.println(Arrays.toString(array)); System.out.println("Minore: " + orderStatistics(array, 1)); System.out.println("Maggiore: " + orderStatistics(array, 10)); while (true) { try { choice = Integer.parseInt(JOptionPane.showInputDialog("Enter an integer between 1 and 10")); if (choice < 0 || choice > 9) { throw new NumberFormatException("Rango non valido"); } break; } catch (NumberFormatException e) { System.out.println("[ERR] " + e.getMessage()); } } System.out.println("Elemento di rango " + choice + " = " + orderStatistics(array, choice)); } public static int orderStatistics(int[] A, int rank) { return randSelect(A, 0, A.length - 1, rank); } /* * Selects the element of given rank * A: array * p: start index * q: end index */ public static int randSelect(int[] A, int p, int q, int rank) { if (p == q) /* subarray with just one element */ { return A[p]; /* there is no other choice, so no matter what rank is requested, A[p] is always the answer */ } int r = partition(A, p, q); int k = r - p + 1; if (rank == k) /* we're lucky, the pivot is the element we're looking for */ { return A[r]; } if (rank < k) /* left subarray */ { return randSelect(A, p, r-1, rank); } return randSelect(A, r+1, q, rank-k); } /* * The same old function as in quicksort, see there for * explanations */ public static int partition(int[] A, int p, int q) { int pivot = A[p]; int i = p; int j; for (j = p+1; j <= q; j++) { if (A[j] <= pivot) { i++; swap(A, i, j); } } swap(A, p, i); return i; } public static void swap(int[] A, int index1, int index2) { int temp = A[index1]; A[index1] = A[index2]; A[index2] = temp; } }