Open In App

K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time

Last Updated : 18 Sep, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

We recommend reading the following posts as a prerequisite for this post.
K’th Smallest/Largest Element in Unsorted Array 
K’th Smallest/Largest Element in Unsorted Array | Expected Linear Time
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
Recommended Practice

In the 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 the 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 the 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 the above algorithm, the last 3 steps are the same as the algorithm in the previous post. The first four steps are used to obtain a good point for partitioning the array (to ensure there are not too many elements on either side of the pivot).
Following is the implementation of the above algorithm. 
 

C++

// C++ implementation of worst case linear time algorithm
// to find k'th smallest element
#include<bits/stdc++.h>
  
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<n/5; i++)
            median[i] = findMedian(arr+l+i*5, 5);
        if (i*5 < n) //For last group with less than 5 elements
        {
            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_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<r; i++)
        if (arr[i] == x)
           break;
    swap(&arr[i], &arr[r]);
  
    // Standard partition algorithm
    i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}
  
// Driver program to test above methods
int main()
{
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    cout << "K'th smallest element is "
         << kthSmallest(arr, 0, n-1, k);
    return 0;
}

                    

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)
{
        Arrays.sort(arr, i, n);
        return arr[i+(n-i)/2];                    // sort the array and 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, l+i*5+5);
              
        // For last group with less than 5 elements
        if (i*5 < n) 
        {
            median[i] = findMedian(arr, l+i*5, 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 and updated by ajayhajare

                    

Python3

# Python3 implementation of worst case  
# linear time algorithm to find 
# k'th smallest element 
  
# Returns k'th smallest element in arr[l..r] 
# in worst case linear time. 
# ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT 
def kthSmallest(arr, l, r, k): 
      
    # If k is smaller than number of 
    # elements in array 
    if (k > 0 and k <= r - l + 1): 
          
        # Number of elements in arr[l..r] 
        n = r - l + 1
  
        # Divide arr[] in groups of size 5, 
        # calculate median of every group
        # and store it in median[] array. 
        median = []
  
        i = 0
        while (i < n // 5):
            median.append(findMedian(arr, l + i * 5, 5))
            i += 1
  
        # For last group with less than 5 elements 
        if (i * 5 < n):
            median.append(findMedian(arr, l + i * 5
                                              n % 5))
            i += 1
  
        # Find median of all medians using recursive call. 
        # If median[] has only one element, then no need 
        # of recursive call
        if i == 1:
            medOfMed = median[i - 1]
        else:
            medOfMed = kthSmallest(median, 0
                                   i - 1, i // 2)
  
        # Partition the array around a medOfMed
        # element and get position of pivot 
        # element in sorted array 
        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 subarray 
            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 the number of 
    # elements in the array 
    return 999999999999
  
def swap(arr, a, b): 
    temp = arr[a] 
    arr[a] = arr[b] 
    arr[b] = temp 
  
# It searches for x in arr[l..r],  
# and partitions the array around x. 
def partition(arr, l, r, x):
    for i in range(l, r):
        if arr[i] == x:
            swap(arr, r, i)
            break
  
    x = arr[r] 
    i =
    for j in range(l, r): 
        if (arr[j] <= x): 
            swap(arr, i, j) 
            i += 1
    swap(arr, i, r) 
    return
  
# A simple function to find 
# median of arr[] from index l to l+n
def findMedian(arr, l, n):
    lis = []
    for i in range(l, l + n):
        lis.append(arr[i])
          
    # Sort the array 
    lis.sort()
  
    # Return the middle element
    return lis[n // 2]
  
# Driver Code 
if __name__ == '__main__'
  
    arr = [12, 3, 5, 7, 4, 19, 26
    n = len(arr) 
    k = 3
    print("K'th smallest element is"
           kthSmallest(arr, 0, n - 1, k)) 
  
# This code is contributed by Ashutosh450

                    

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

                    

Javascript

<script>
// Javascript implementation of worst
// case linear time algorithm
// to find k'th smallest element
  
// 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.
function findMedian(arr, i, n) {
    if (i <= n)
        arr.sort((a, b) => a - b); // Sort the array
    else
        arr.sort((a, b) => a - b);
    let flr = Math.floor(n / 2);
    return arr[flr]; // Return middle element
}
  
// Returns k'th smallest element
// in arr[l..r] in worst case
// linear time. ASSUMPTION: ALL
// ELEMENTS IN ARR[] ARE DISTINCT
function kthSmallest(arr, l, r, k)
{
  
    // If k is smaller than
    // number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        let 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.
        let i;
  
        // There will be floor((n+4)/5) groups;
        let median = new Array(Math.floor((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
        let medOfMed = (i == 1) ? median[i - 1] :
            kthSmallest(median, 0, i - 1, Math.floor(i / 2));
  
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        let 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;
}
  
function swap(arr, i, j) {
    let 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.
function partition(arr, l, r, x) {
    // Search for x in arr[l..r] and move it to end
    let i;
    for (i = l; i < r; i++)
        if (arr[i] == x)
            break;
    swap(arr, i, r);
  
    // Standard partition algorithm
    i = l;
    for (let j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, r);
    return i;
}
  
// Driver code
  
let arr = [12, 3, 5, 7, 4, 19, 26];
let n = arr.length, k = 3;
document.write("K'th smallest element is "
    + kthSmallest(arr, 0, n - 1, k));
  
// This code has been contributed by Saurabh Jaiswal
</script>

                    

Output
K'th smallest element is 5

The code implements the “Worst-case linear time algorithm to find the k-th smallest element” using the Decrease and Conquer strategy. The steps of the algorithm are as follows:

If the value of k is greater than the number of elements in the array or k is less than 1, return INT_MAX (which is a constant representing the maximum value of an integer in C++).

Divide the array into groups of five elements each (except possibly the last group, which may have less than five elements). Sort each group and find its median. Store all the medians in an array called ‘median’.

Find the median of the ‘median’ array by recursively calling the kthSmallest() function. If the ‘median’ array has only one element, then it is the median of all medians.

Partition the original array around the median of medians and find the position ‘pos’ of the pivot element in the sorted array.

If pos-l is equal to k-1 (i.e., the pivot element is the k-th smallest element), return the pivot element.

If pos-l is greater than k-1, then recursively call the kthSmallest() function on the left sub-array (i.e., arr[l…pos-1]).

If pos-l is less than k-1, then recursively call the kthSmallest() function on the right sub-array (i.e., arr[pos+1…r]) with updated k value (k-(pos-l+1)).
Time Complexity: 
The worst-case time complexity of the above algorithm is O(n). Let us analyze all steps. 
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. 
Step (3) takes T(n/5) time. Step (4) is a 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 the maximum number of elements greater than medOfMed (obtained in step 3) or the 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. 
3\left (\left \lceil \frac{1}{2}\left \lceil \frac{n}{5} \right \rceil \right \rceil-2 \right )\geq \frac{3n}{10}-6
Similarly, the number of elements which 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 and that any input of 80 or fewer elements requires O(1) time. We can therefore obtain the recurrence 
T(n)\leq \begin{cases} \Theta (1) & \text{ if } n\leq 80 \\ T(\left \lceil \frac{n}{5} \right \rceil)+T(\frac{7n}{10}+6)+O(n) & \text{ if } n> 90 \end{cases}
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
Note that the above algorithm is linear in the 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 is preferred.


 



Previous Article
Next Article

Similar Reads

Can QuickSort be implemented in O(nLogn) worst case time complexity?
The worst-case time complexity of a typical implementation of QuickSort is O(n2). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when the input array is sorted or reverses sorted and either the first or last element is picked as a pivot. Although randomized QuickSort works well even when
15+ min read
K’th Smallest/Largest Element in Unsorted Array | Expected Linear Time
Prerequisite: K’th Smallest/Largest Element in Unsorted Array | Set 1 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 = 3Output: 7 Input: arr[] = {7, 10, 4, 3,
13 min read
K'th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
Given an array and a number k where k is smaller than the size of the array, we need to find the k’th largest element in the given array. It is given that all array elements are distinct. We recommend reading the following post as a prerequisite to this post. K’th Smallest/Largest Element in Unsorted Array | Set 1 Examples: Input: arr[] = {7, 10, 4
9 min read
When does the worst case of Quicksort occur?
The answer depends on the strategy for choosing pivot. In early versions of Quick Sort where the leftmost (or rightmost) element is chosen as a pivot, the worst occurs in the following cases. 1) Array is already sorted in the same order. 2) Array is already sorted in reverse order. 3) All elements are the same (a special case of cases 1 and 2) Sinc
4 min read
QuickSort Tail Call Optimization (Reducing worst case space to Log n )
Prerequisite : Tail Call Elimination In QuickSort, partition function is in-place, but we need extra space for recursive function calls. A simple implementation of QuickSort makes two calls to itself and in worst case requires O(n) space on function call stack. The worst case happens when the selected pivot always divides the array such that one pa
12 min read
Cuckoo Hashing - Worst case O(1) Lookup!
Background : There are three basic operations that must be supported by a hash table (or a dictionary): Lookup(key): return true if key is there on the table, else falseInsert(key): add the item ‘key’ to the table if not already presentDelete(key): removes ‘key’ from the table Collisions are very likely even if we have a big table to store keys. Us
15+ min read
Find a permutation that causes worst case of Merge Sort
Given a set of elements, find which permutation of these elements would result in worst case of Merge Sort.Asymptotically, merge sort always takes O(n Log n) time, but the cases that require more comparisons generally take more time in practice. We basically need to find a permutation of input elements that would lead to maximum number of compariso
12 min read
Worst, Average and Best Case Analysis of Algorithms
In the previous post, we discussed how Asymptotic analysis overcomes the problems of the naive way of analyzing algorithms. But let's take an overview of the asymptotic notation and learn about What is Worst, Average, and Best cases of an algorithm: Popular Notations in Complexity Analysis of Algorithms1. Big-O NotationWe define an algorithm’s wors
14 min read
Finding Median of unsorted Array in linear time using C++ STL
Given an unsorted array arr[] having N elements, the task is to find out the median of the array in linear time complexity. Examples: Input: N = 5, arr[] = {4, 1, 2, 6, 5} Output: 4 Explanation: Since N = 5, which is odd, therefore the median is the 3rd element in the sorted array. The 3rd element in the sorted arr[] is 4. Hence the median is 4. In
3 min read
Convert camel case string to snake case in Java
Given a string in camel case, the task is to write a Java program to convert the given string from camel case to snake case and print the modified string. Examples: Input: GeeksForGeeks Output: geeks_for_geeks Input: CamelCaseToSnakeCase Output: camel_case_to_snake_case Method 1: Naive Approach First we initialize a variable 'result' with an empty
3 min read
three90RightbarBannerImg