FOR FREE MATERIALS

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 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.

Code

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]);

               }

 

 

SPACE COMPLEXITY:

Contributed by