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.

```
#include <stdio.h>
```
```
#include <string.h>
```

int partition(int* a, int low, int high)

```
{
```
```
    int left = low;
```

    int pivotIdx = low + (high - low)/2;

```
    int pivot = a[pivotIdx];
```
```
    a[pivotIdx] = a[high];
```
```
    a[high] = pivot;
```
```
    pivotIdx = high;
```
```
    int partitionIdx = low;
```
```
    while (left < high)
```
```
    {
```
```
        if (a[left] < pivot) 
```
```
        {
```
```
            int tmp = a[left];
```
```
            a[left] = a[partitionIdx];
```
```
            a[partitionIdx] = tmp;
```
```
            ++partitionIdx;
```
```
        }
```
```
        ++left;
```
```
    }
```
```
    a[pivotIdx] = a[partitionIdx];
```
```
    a[partitionIdx] = pivot;
```
```
    return partitionIdx;
```
```
}
```
```
 
```

int quickselect(int* a, int low, int high, int k)

```
{
```
```
    if (low == high)
```
```
        return a[low];
```

    int pivotIdx = partition(a, low, high);

    int sizeOfLeftSubArray = pivotIdx - low + 1;

```
    if (sizeOfLeftSubArray > k)
```
```
    {
```

        return quickselect(a, low, pivotIdx-1, k);

```
    }
```
```
    else if (sizeOfLeftSubArray < k)
```
```
    {
```

        return quickselect(a, pivotIdx+1, high, k-sizeOfLeftSubArray);

```
    }
```
```
    else
```
```
    {
```
```
        return a[pivotIdx];
```
```
    }
```
```
}
```
```
int main()
```
```
{
```

  int arr[] = {4, 5, 22, 49, 64, 43, 32 , 323, 78, 90};

```
  int k;
```

  printf("\nEnter the number 'k' to find the 'kth' largest element: ");

```
  scanf("%d", &k);
```

  printf("\nKth largest element is %d", quickselect(arr, 0, 9, k));

```
  return 0;
```
```
}
```

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

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

« Prev - C Program to Perform Uniform Binary Search

» Next - C Program to Search Sorted Sequence using Divide and Conquer

Related Posts:

Recommended Articles: