## Kth Largest and Smallest Element

Back to Programming

### Description

The program is written to find the kth largest or kth smallest element from the list/array. The elements of the list are taken as input and the value of k is also given by the user. One extra variable is taken to identify whether the user wants to get kth largest element of kth smallest element. If the value of the variable is 1 then kth largest element is printed else kth smallest element will be printed.

For sorting the list, bubble sort is used here. Here, for loops are used to traverse the array or list while finding the kth largest or kth smallest, so, only the single line loops are written. But in python program ‘m = 0’ is written inside for loops just to maintain the proper indentation, it does not have any significance in finding the kth largest or kth smallest element.

### Algorithm

INPUT: The array elements, value of k, largest or smallest element which is to be found

OUTPUT: The kth largest/smallest element according to the condition.

PROCESS:

Step 1: [Taking the inputs]

Read n [number of elements]

For i=0 to n-1 repeat

Read l [1 for kth largest / 0 for kth smallest]

Step 2: [Sorting and finding the kth largest/kth smallest]

For i=0 to n-1 repeat

For j=0 to n-i-2 repeat

If a[j]>a[j+1] then

Set t<-a[j]

Set a[j]<-a[j+1]

Set a[j+1]<-t

[End of ‘if’]

[End of ‘for’ loop]

[End of ‘for’ loop]

[Printing the sorted array]

Print "The sorted list is: "

For i=0 to n-1 repeat

Print a[i]

[End of ‘for’ loop]

[Finding the kth largest element]

If l==1 then

[Pointing to the kth largest element]

For i=n-1 to n-k repeat the loop

[End of ‘for’ loop]

Print "The kth largest element is: a[i+1]”

[End of ‘if’]

[Finding the kth smallest element]

Else

[Pointing to the kth smallest element]

For i=0 to k-1 repeat the loop

[End of ‘for’ loop]

Print "The kth smallest element is: a[i-1]”

[End of ‘else’]

Step 3: Stop.

## TIME COMPLEXITY:

if(l==1) --------------------------------------- O(1)

{              //pointing to the kth largest element

for(i=n-1;i>=n-k;i--); -------------------- O(n)

printf("\nThe %dth largest element is: %d",k,a[i+1]);

}

//finding the kth smallest element

else

{              //pointing to the kth smallest element

for(i=0;i<k;i++); -------------------------- O(n)

printf("\nThe %dth smallest element is: %d",k,a[i-1]);

}

Related

Contributed by