C Program to Find kth Largest Element in a Sequence

This C program finds the kth largest element in a sequence.

QuickSelect, a variant of quicksort algorithm is used to find the kth largest element in a sequence in O(n) time.

Here is the source code of the C program to find the kth largest element in a sequence. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <string.h>
  3. int partition(int* a, int low, int high)
  4. {
  5.     int left = low;
  6.     int pivotIdx = low + (high - low)/2;
  7.     int pivot = a[pivotIdx];
  8.     a[pivotIdx] = a[high];
  9.     a[high] = pivot;
  10.     pivotIdx = high;
  11.     int partitionIdx = low;
  12.     while (left < high)
  13.     {
  14.         if (a[left] < pivot) 
  15.         {
  16.             int tmp = a[left];
  17.             a[left] = a[partitionIdx];
  18.             a[partitionIdx] = tmp;
  19.             ++partitionIdx;
  20.         }
  21.         ++left;
  22.     }
  23.     a[pivotIdx] = a[partitionIdx];
  24.     a[partitionIdx] = pivot;
  25.     return partitionIdx;
  26. }
  27.  
  28. int quickselect(int* a, int low, int high, int k)
  29. {
  30.     if (low == high)
  31.         return a[low];
  32.     int pivotIdx = partition(a, low, high);
  33.     int sizeOfLeftSubArray = pivotIdx - low + 1;
  34.     if (sizeOfLeftSubArray > k)
  35.     {
  36.         return quickselect(a, low, pivotIdx-1, k);
  37.     }
  38.     else if (sizeOfLeftSubArray < k)
  39.     {
  40.         return quickselect(a, pivotIdx+1, high, k-sizeOfLeftSubArray);
  41.     }
  42.     else
  43.     {
  44.         return a[pivotIdx];
  45.     }
  46. }
  47. int main()
  48. {
  49.   int arr[] = {4, 5, 22, 49, 64, 43, 32 , 323, 78, 90};
  50.   int k;
  51.   printf("\nEnter the number 'k' to find the 'kth' largest element: ");
  52.   scanf("%d", &k);
  53.   printf("\nKth largest element is %d", quickselect(arr, 0, 9, k));
  54.   return 0;
  55. }

$ gcc kthlargest.c -o kthlargest
$ ./kthlargest
 
Enter the number 'k' to find the 'kth' largest element: 2
 
Kth largest element is 5

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.