C Program to Find kth Smallest Element in Array using Partitioning

This is a C Program to find kth smallest element by method of partitioning. The same partitioning function which is used for Quicksort algorithm can be used.

Here is source code of the C Program to Find kth Smallest Element by the Method of Partitioning the Array. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<math.h>
```
```
#include<time.h>
```
```
#include<stdlib.h>
```
```
 
```
```
int N = 20;
```
```
int A[20];
```
```
 
```
```
void swap(int dex1, int dex2) {
```
```
    int temp = A[dex1];
```
```
    A[dex1] = A[dex2];
```
```
    A[dex2] = temp;
```
```
}
```
```
 
```
```
int partition(int start, int end) {
```
```
    int i = start + 1;
```
```
    int j = i;
```
```
    int pivot = start;
```
```
    for (; i < end; i++) {
```
```
        if (A[i] < A[pivot]) {
```
```
            swap(i, j);
```
```
            j++;
```
```
        }
```
```
    }
```
```
    if (j <= end)
```
```
        swap(pivot, (j - 1));
```
```
 
```
```
    return j - 1;
```
```
}
```
```
 
```

void quick_sort(int start, int end, int K) {

```
    int part;
```
```
    if (start < end) {
```
```
        part = partition(start, end);
```
```
        if (part == K - 1)
```

            printf("kth smallest element : %d ", A[part]);

```
        if (part > K - 1)
```
```
            quick_sort(start, part, K);
```
```
        else
```

            quick_sort(part + 1, end, K);

```
    }
```
```
    return;
```
```
}
```
```
 
```
```
int main(int argc, char **argv) {
```
```
    int i;
```
```
    time_t seconds;
```
```
    time(&seconds);
```
```
    srand((unsigned int) seconds);
```
```
 
```
```
    for (i = 0; i < N; i++)
```

        A[i] = rand() % (1000 - 1 + 1) + 1;

```
 
```

    printf("The original sequence is:  ");

```
    for (i = 0; i < N; i++)
```
```
        printf("%d ", A[i]);
```
```
 
```

    printf("\nEnter the Kth smallest you want to find: ");

```
    int k;
```
```
    scanf("%d", &k);
```
```
    quick_sort(0, N, k);
```
```
}
```

Output:

$ gcc KthSmallestUsingPartitioning.c
$ ./a.out
 
The original sequence is:  909 967 552 524 735 383 616 718 904 945 730 173 143 954 482 307 228 35 224 703 
Enter the Kth smallest you want to find: 3
kth smallest element : 173

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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]

« Prev - C Program to Implement Quick Sort with Given Complexity Constraint

» Next - C program to sort integers using Bubble Sort

Related Posts:

Recommended Articles: