selection alg

This is a simple Java implementation of the selection algorithm (partition based), which is a variation of the well known Quick-Sort.
In Quick-Sort we call both branches, but in this case we can call one because we know in which partition our target element is. The average complexity of this approach is O(N). But worst case complexity is  O(N^2), if we choose bad pivots.
The code below will return k=8 with this call (Note it starts counting in 0):
int[] arr = { 9, -5, 1, 5, 8, 7, 99, 9098, 3, 2 };
int k = t.kthLargest(arr, 0, 9, 3);

The worst case is when the pivot leaves all elements in one side and one in the other:
t(n)=t(n-1)+o(n) => O(N^2)
For the average (equal sized partitions) case we have
t(n)=t(n/2)+o(n) => O(N)

public void swap(int arr[], int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	public int partition(int arr[], int left, int right, int pivoteIndex) {
		int pivotValue = arr[pivoteIndex];
		swap(arr, pivoteIndex, right); // Move pivot to end
		int swapIndex = left;
		for (int i = left; i < right; i++)
			if (arr[i] > pivotValue) { // Change for < to change the order
				swap(arr, swapIndex, i);
				swapIndex++;
			}
		swap(arr, right, swapIndex); // Move pivot to its final place
		return swapIndex;
	}

	public int kthLargest(int arr[], int left, int right, int k) {
		int pivoteIndex;
		int pivoteD;
		if (left == right)
			return arr[left];
		while (true) {
			pivoteIndex = left + (int) (Math.random() * ((right - left) + 1)); //Random number between left and right
			pivoteIndex = partition(arr, left, right, pivoteIndex);
			pivoteD = pivoteIndex - left + 1;
			if (k == pivoteD)
				return arr[k];
			else if (k < pivoteD)
				kthLargest(arr, left, pivoteIndex - 1, k);
			else
				kthLargest(arr, pivoteIndex + 1, right, k - pivoteD);
		}
	}

A better algorithm is called Median of Medians, which ensures O(N) as the worst case because the pivot chosen is greater than or less than at least 30% of the elements.