# K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)

We recommend reading following posts as a prerequisite of this post.

Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.

Examples:

```Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10```

In previous post, we discussed an expected linear time algorithm. In this post, a worst-case linear time method is discussed. The idea in this new method is similar to quickSelect(), we get worst-case linear time by selecting a pivot that divides array in a balanced way (there are not very few elements on one side and many on another side). After the array is divided in a balanced way, we apply the same steps as used in quickSelect() to decide whether to go left or right of the pivot.

Following is complete algorithm.

```kthSmallest(arr[0..n-1], k)
1) Divide arr[] into ⌈n/5⌉ groups where size of each group is 5
except possibly the last group which may have less than 5 elements.

2) Sort the above created ⌈n/5⌉ groups and find median
of all groups. Create an auxiliary array 'median[]' and store medians
of all ⌈n/5⌉ groups in this median array.

// Recursively call this method to find median of median[0..⌈n/5⌉-1]
3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

4) Partition arr[] around medOfMed and obtain its position.
pos = partition(arr, n, medOfMed)

5) If pos == k return medOfMed
6) If pos > k return kthSmallest(arr[l..pos-1], k)
7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)```

In above algorithm, last 3 steps are same as algorithm in previous post. The first four steps are used to obtain a good point for partitioning the array (to make sure that there are not too many elements either side of pivot).

Following is the implementation of above algorithm.

## C++

 `// C++ implementation of worst case linear time algorithm ` `// to find k'th smallest element ` `#include ` `#include ` `#include ` ` `  `using` `namespace` `std; ` ` `  `int` `partition(``int` `arr[], ``int` `l, ``int` `r, ``int` `k); ` ` `  `// A simple function to find median of arr[].  This is called ` `// only for an array of size 5 in this program. ` `int` `findMedian(``int` `arr[], ``int` `n) ` `{ ` `    ``sort(arr, arr+n);  ``// Sort the array ` `    ``return` `arr[n/2];   ``// Return middle element ` `} ` ` `  `// Returns k'th smallest element in arr[l..r] in worst case ` `// linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT ` `int` `kthSmallest(``int` `arr[], ``int` `l, ``int` `r, ``int` `k) ` `{ ` `    ``// If k is smaller than number of elements in array ` `    ``if` `(k > 0 && k <= r - l + 1) ` `    ``{ ` `        ``int` `n = r-l+1; ``// Number of elements in arr[l..r] ` ` `  `        ``// Divide arr[] in groups of size 5, calculate median ` `        ``// of every group and store it in median[] array. ` `        ``int` `i, median[(n+4)/5]; ``// There will be floor((n+4)/5) groups; ` `        ``for` `(i=0; i k-1)  ``// If position is more, recur for left ` `            ``return` `kthSmallest(arr, l, pos-1, k); ` ` `  `        ``// Else recur for right subarray ` `        ``return` `kthSmallest(arr, pos+1, r, k-pos+l-1); ` `    ``} ` ` `  `    ``// If k is more than number of elements in array ` `    ``return` `INT_MAX; ` `} ` ` `  `void` `swap(``int` `*a, ``int` `*b) ` `{ ` `    ``int` `temp = *a; ` `    ``*a = *b; ` `    ``*b = temp; ` `} ` ` `  `// It searches for x in arr[l..r], and partitions the array  ` `// around x. ` `int` `partition(``int` `arr[], ``int` `l, ``int` `r, ``int` `x) ` `{ ` `    ``// Search for x in arr[l..r] and move it to end ` `    ``int` `i; ` `    ``for` `(i=l; i

## Java

 `// Java implementation of worst  ` `// case linear time algorithm ` `// to find k'th smallest element ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` ` `  `// int partition(int arr[], int l, int r, int k); ` ` `  `// A simple function to find median of arr[]. This is called ` `// only for an array of size 5 in this program. ` `static` `int` `findMedian(``int` `arr[], ``int` `i,``int` `n) ` `{ ` `    ``if``(i <= n) ` `        ``Arrays.sort(arr, i, n); ``// Sort the array ` `    ``else` `        ``Arrays.sort(arr, n, i); ` `    ``return` `arr[n/``2``]; ``// Return middle element ` `} ` ` `  `// Returns k'th smallest element ` `// in arr[l..r] in worst case ` `// linear time. ASSUMPTION: ALL  ` `// ELEMENTS IN ARR[] ARE DISTINCT ` `static` `int` `kthSmallest(``int` `arr[], ``int` `l, ``int` `r, ``int` `k) ` `{ ` `    ``// If k is smaller than  ` `    ``// number of elements in array ` `    ``if` `(k > ``0` `&& k <= r - l + ``1``) ` `    ``{ ` `        ``int` `n = r - l + ``1` `; ``// Number of elements in arr[l..r] ` ` `  `        ``// Divide arr[] in groups of size 5,  ` `        ``// calculate median of every group ` `        ``//  and store it in median[] array. ` `        ``int` `i; ` `         `  `         ``// There will be floor((n+4)/5) groups; ` `        ``int` `[]median = ``new` `int``[(n + ``4``) / ``5``]; ` `        ``for` `(i = ``0``; i < n/``5``; i++) ` `            ``median[i] = findMedian(arr,l + i * ``5``, ``5``); ` `             `  `        ``// For last group with less than 5 elements ` `        ``if` `(i*``5` `< n)  ` `        ``{ ` `            ``median[i] = findMedian(arr,l + i * ``5``, n % ``5``);  ` `            ``i++; ` `        ``}  ` ` `  `        ``// Find median of all medians using recursive call. ` `        ``// If median[] has only one element, then no need ` `        ``// of recursive call ` `        ``int` `medOfMed = (i == ``1``)? median[i - ``1``]: ` `                                ``kthSmallest(median, ``0``, i - ``1``, i / ``2``); ` ` `  `        ``// Partition the array around a random element and ` `        ``// get position of pivot element in sorted array ` `        ``int` `pos = partition(arr, l, r, medOfMed); ` ` `  `        ``// If position is same as k ` `        ``if` `(pos-l == k - ``1``) ` `            ``return` `arr[pos]; ` `        ``if` `(pos-l > k - ``1``) ``// If position is more, recur for left ` `            ``return` `kthSmallest(arr, l, pos - ``1``, k); ` ` `  `        ``// Else recur for right subarray ` `        ``return` `kthSmallest(arr, pos + ``1``, r, k - pos + l - ``1``); ` `    ``} ` ` `  `    ``// If k is more than number of elements in array ` `    ``return` `Integer.MAX_VALUE; ` `} ` ` `  `static` `int``[] swap(``int` `[]arr, ``int` `i, ``int` `j) ` `{ ` `    ``int` `temp = arr[i]; ` `    ``arr[i] = arr[j]; ` `    ``arr[j] = temp; ` `    ``return` `arr; ` `} ` ` `  `// It searches for x in arr[l..r], and  ` `// partitions the array around x. ` `static` `int` `partition(``int` `arr[], ``int` `l, ` `                        ``int` `r, ``int` `x) ` `{ ` `    ``// Search for x in arr[l..r] and move it to end ` `    ``int` `i; ` `    ``for` `(i = l; i < r; i++) ` `        ``if` `(arr[i] == x) ` `        ``break``; ` `    ``swap(arr, i, r); ` ` `  `    ``// Standard partition algorithm ` `    ``i = l; ` `    ``for` `(``int` `j = l; j <= r - ``1``; j++) ` `    ``{ ` `        ``if` `(arr[j] <= x) ` `        ``{ ` `            ``swap(arr, i, j); ` `            ``i++; ` `        ``} ` `    ``} ` `    ``swap(arr, i, r); ` `    ``return` `i; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args) ` `{ ` `    ``int` `arr[] = {``12``, ``3``, ``5``, ``7``, ``4``, ``19``, ``26``}; ` `    ``int` `n = arr.length, k = ``3``; ` `    ``System.out.println(``"K'th smallest element is "` `        ``+ kthSmallest(arr, ``0``, n - ``1``, k)); ` `} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

## C#

 `// C# implementation of worst  ` `// case linear time algorithm  ` `// to find k'th smallest element  ` `using` `System; ` ` `  `class` `GFG  ` `{  ` ` `  `// int partition(int arr[], int l, int r, int k);  ` ` `  `// A simple function to find median of arr[]. This is called  ` `// only for an array of size 5 in this program.  ` `static` `int` `findMedian(``int` `[]arr, ``int` `i, ``int` `n)  ` `{  ` `    ``if``(i <= n)  ` `        ``Array.Sort(arr, i, n); ``// Sort the array  ` `    ``else` `        ``Array.Sort(arr, n, i);  ` `    ``return` `arr[n/2]; ``// Return middle element  ` `}  ` ` `  `// Returns k'th smallest element  ` `// in arr[l..r] in worst case  ` `// linear time. ASSUMPTION: ALL  ` `// ELEMENTS IN ARR[] ARE DISTINCT  ` `static` `int` `kthSmallest(``int` `[]arr, ``int` `l, ` `                            ``int` `r, ``int` `k)  ` `{  ` `    ``// If k is smaller than  ` `    ``// number of elements in array  ` `    ``if` `(k > 0 && k <= r - l + 1)  ` `    ``{  ` `        ``int` `n = r - l + 1 ; ``// Number of elements in arr[l..r]  ` ` `  `        ``// Divide arr[] in groups of size 5,  ` `        ``// calculate median of every group  ` `        ``// and store it in median[] array.  ` `        ``int` `i;  ` `         `  `        ``// There will be floor((n+4)/5) groups;  ` `        ``int` `[]median = ``new` `int``[(n + 4) / 5];  ` `        ``for` `(i = 0; i < n/5; i++)  ` `            ``median[i] = findMedian(arr, l + i * 5, 5);  ` `             `  `        ``// For last group with less than 5 elements  ` `        ``if` `(i*5 < n)  ` `        ``{  ` `            ``median[i] = findMedian(arr,l + i * 5, n % 5);  ` `            ``i++;  ` `        ``}  ` ` `  `        ``// Find median of all medians using recursive call.  ` `        ``// If median[] has only one element, then no need  ` `        ``// of recursive call  ` `        ``int` `medOfMed = (i == 1)? median[i - 1]:  ` `                                ``kthSmallest(median, 0, i - 1, i / 2);  ` ` `  `        ``// Partition the array around a random element and  ` `        ``// get position of pivot element in sorted array  ` `        ``int` `pos = partition(arr, l, r, medOfMed);  ` ` `  `        ``// If position is same as k  ` `        ``if` `(pos-l == k - 1)  ` `            ``return` `arr[pos];  ` `        ``if` `(pos-l > k - 1) ``// If position is more, recur for left  ` `            ``return` `kthSmallest(arr, l, pos - 1, k);  ` ` `  `        ``// Else recur for right subarray  ` `        ``return` `kthSmallest(arr, pos + 1, r, k - pos + l - 1);  ` `    ``}  ` ` `  `    ``// If k is more than number of elements in array  ` `    ``return` `int``.MaxValue;  ` `}  ` ` `  `static` `int``[] swap(``int` `[]arr, ``int` `i, ``int` `j)  ` `{  ` `    ``int` `temp = arr[i];  ` `    ``arr[i] = arr[j];  ` `    ``arr[j] = temp;  ` `    ``return` `arr;  ` `}  ` ` `  `// It searches for x in arr[l..r], and  ` `// partitions the array around x.  ` `static` `int` `partition(``int` `[]arr, ``int` `l,  ` `                        ``int` `r, ``int` `x)  ` `{  ` `    ``// Search for x in arr[l..r] and move it to end  ` `    ``int` `i;  ` `    ``for` `(i = l; i < r; i++)  ` `        ``if` `(arr[i] == x)  ` `        ``break``;  ` `    ``swap(arr, i, r);  ` ` `  `    ``// Standard partition algorithm  ` `    ``i = l;  ` `    ``for` `(``int` `j = l; j <= r - 1; j++)  ` `    ``{  ` `        ``if` `(arr[j] <= x)  ` `        ``{  ` `            ``swap(arr, i, j);  ` `            ``i++;  ` `        ``}  ` `    ``}  ` `    ``swap(arr, i, r);  ` `    ``return` `i;  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `Main(String[] args)  ` `{  ` `    ``int` `[]arr = {12, 3, 5, 7, 4, 19, 26};  ` `    ``int` `n = arr.Length, k = 3;  ` `    ``Console.WriteLine(``"K'th smallest element is "` `        ``+ kthSmallest(arr, 0, n - 1, k));  ` `}  ` `}  ` ` `  `// This code contributed by Rajput-Ji `

Output:

`K'th smallest element is 5`

Time Complexity:
The worst case time complexity of the above algorithm is O(n). Let us analyze all steps.

The steps 1) and 2) take O(n) time as finding median of an array of size 5 takes O(1) time and there are n/5 arrays of size 5.
The step 3) takes T(n/5) time. The step 4 is standard partition and takes O(n) time.
The interesting steps are 6) and 7). At most, one of them is executed. These are recursive steps. What is the worst case size of these recursive calls. The answer is maximum number of elements greater than medOfMed (obtained in step 3) or maximum number of elements smaller than medOfMed.
How many elements are greater than medOfMed and how many are smaller?
At least half of the medians found in step 2 are greater than or equal to medOfMed. Thus, at least half of the n/5 groups contribute 3 elements that are greater than medOfMed, except for the one group that has fewer than 5 elements. Therefore, the number of elements greater than medOfMed is at least.

Similarly, the number of elements that are less than medOfMed is at least 3n/10 – 6. In the worst case, the function recurs for at most n – (3n/10 – 6) which is 7n/10 + 6 elements.

Note that 7n/10 + 6 20 20 and that any input of 80 or fewer elements requires O(1) time. We can therefore obtain the recurrence

We show that the running time is linear by substitution. Assume that T(n) cn for some constant c and all n > 80. Substituting this inductive hypothesis into the right-hand side of the recurrence yields

```T(n)  <= cn/5 + c(7n/10 + 6) + O(n)
<= cn/5 + c + 7cn/10 + 6c + O(n)
<= 9cn/10 + 7c + O(n)
<= cn, ```

since we can pick c large enough so that c(n/10 – 7) is larger than the function described by the O(n) term for all n > 80. The worst-case running time of is therefore linear (Source: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10.htm ).

Note that the above algorithm is linear in worst case, but the constants are very high for this algorithm. Therefore, this algorithm doesn’t work well in practical situations, randomized quickSelect works much better and preferred.