Array Sorting – Kth largest Element

Input Array: {7,1,2,12,4,5,6,15,8,9}

Find the Kth largest element.

Solution one:

Algorithm:

1. Sort array
2. array[k] is the kth largest element

First sort the array:

There are many sorting techniques available. Most of the people use the bubble sort in the interviews as they feel it is easy. But most of the interviewers in the product based companies expect you to solve the code using other sorting techniques. As if you see the bubble sort the complexity is high

Better use selection sort or Quick Sort for solving this.

If you use quick you will get more impression as most of the candidates who appear for the interview won’t be able to write quicksort as it is little difficult to understand

Array After sorting: {1,2,4,5,6,7,8,9,12,15}

Now the Kth largest element is array[k]

Implementation:

Quick Sort:

public void kthlargestElement(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
length = inputArr.length;
int [] array = quickSort(inputArr,length,0, length - 1);

}

private int[] quickSort(int[] array, int lenght, int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];
while (i <= j) { while (array[i] < pivot) { i++; } while (array[j] > pivot) {
j--;
}
if (i <= j) { exchangeNumbers(i, j); i++; j--; } } if (lowerIndex < j){ quickSort(lowerIndex, j); } if (i < higherIndex){ quickSort(i, higherIndex); } } private void exchangeNumbers(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }

Leave a Reply

Your email address will not be published. Required fields are marked *