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.
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 a[i]
Read k
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.
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