The question
Given an array of integers find the kth element in the sorted order (not the kth distinct element). So, if the array is [3, 1, 2, 1, 4] and k is 3 then the result is 2, because it’s the 3rd element in sorted order (but the 3rd distinct element is 3).
My solution
This doesn’t sound as a very hard problem but I couldn’t find a solution better than:
– Sort using quicksort
– Return the element at index k
The complexity of this solution is the complexity of quicksort O(nlogn).
The best solution
The best solution is a family of algorithms called “selection algorithm” which serves exactly this purpose. Most specifically quickselect can be used:
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
var arr = [1, 5, 6, 6, 9, 2, 3, 3, 4, 3, 1, 9, 4, 5, 7, 7, 1];
function partition(arr, left, right, pivot) {
// Move pivot to the end
var tmp;
tmp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = tmp;
// This is the index that divides lower and higher numbers
var swapIndex = left;
for (var i = left; i < right; i++) {
// Check if current value is lower than pivot value
if (arr[i] < arr[right]) {
tmp = arr[i];
arr[i] = arr[swapIndex];
arr[swapIndex] = tmp;
swapIndex++;
}
}
// Move pivot value to where it should be
tmp = arr[right];
arr[right] = arr[swapIndex];
arr[swapIndex] = tmp;
return swapIndex;
}
function select(arr, left, right, k) {
// I don't care very much about the pivot now. I'm just choosing the middle.
var pivot = parseInt((left + right) / 2, 10);
var res = partition(arr, left, right, pivot);
if (res === k) {
return arr[res];
}
if (k < res) {
return select(arr, left, res - 1, k);
} else {
return select(arr, res + 1, right, k);
}
}
function test() {
var found = select(arr, 0, arr.length -1, 6);
if (found === 3) {
console.log('success');
}
}
test(); // Prints success
computer_science algorithms javascript programming