How will you Write a c program to find the kth smallest element in an array in c?

Answer 1

//This is for kth largest element. (So this is for n-k smallest element) //Sudipta Kundu [Wipro Technologies] #include <stdio.h> //Input: array with index range [first, last)

//Output: new index of the pivot. An element in the middle is chosen to be a pivot. Then the array's elements are

//placed in such way that all elements <= pivot are to the left and all elements >= pivot are to the right.

int positionPivot(int* array, int first, int last); //Input: array with index range [first, last) and integer K (first <= K < last)

//Output: array whose Kth element (i.e. array[K]) has the "correct" position. More precisely,

//array[first ... K - 1] <= array[K] <= array[K + 1 ... last - 1]

void positionKthElement(int* array, int first, int last, int k); int main() {

int array[] = {7,1,8,3,1,9,4,8};

int i;

for (i = 0; i < 8; i++) {

positionKthElement(array, 0, sizeof(array) / sizeof(array[0]),i);

printf("%d is at position %d\n", array[i], i);

}

return 0;

}

int positionPivot(int* array, int first, int last) {

if (first last)

return first; int tmp = (first + last) / 2;

int pivot = array[tmp];

int movingUp = first + 1;

int movingDown = last - 1;

array[tmp] = array[first];

array[first] = pivot;

while (movingUp <= movingDown) {

while (movingUp <= movingDown && array[movingUp] < pivot)

++movingUp;

while (pivot < array[movingDown])

--movingDown;

if (movingUp <= movingDown) {

tmp = array[movingUp];

array[movingUp] = array[movingDown];

array[movingDown] = tmp;

++movingUp;

--movingDown;

}

}

array[first] = array[movingDown];

array[movingDown] = pivot;

return movingDown;

} void positionKthElement(int* array, int first, int last, int k) {

int index;

while ((index = positionPivot(array, first, last)) != k) {

if (k < index)

last = index;

else

first = index + 1;

}

}

Answer 2

1) Use any method you like, for example a bubble sort or a quick sort, to sort the array in ascending order.

2) Pick the kth element.