Function kthSmallest

CPP/arrays/KthSmallest.cpp:35–71

Returns kth smallest element in arr[] in worst case linear time

// Returns kth smallest element in arr[] in worst case linear time
int kthSmallest(int arr[], int l, int r, int k) {
   // If k is smaller than number of elements in array
   if (k > 0 && k <= r - l + 1) {
       int n = r - l + 1;

       // Divide arr[] in groups of size 5, calculate median
       // of every group and store it in median[] array
       int i, median[(n + 4) / 5];
       for (i = 0; i < n / 5; i++)
           median[i] = findMedian(arr + l + i * 5, 5);
       // For the last group
       if (i * 5 < n) {
           median[i] = findMedian(arr + l + i * 5, n % 5);
           i++;
       }

       // Find median of all medians using recursive call
       int medOfMed = (i == 1) ? median[i - 1] : kthSmallest(median, 0, i - 1, i / 2);

       // Partitioning the array around a random element and
       // get position of pivot element in sorted array
       int pos = partition(arr, l, r, medOfMed);

       // If position is same as k
       if (pos - l == k - 1)
           return arr[pos];
       // If position is more, recur for left
       if (pos - l > k - 1)
           return kthSmallest(arr, l, pos - 1, k);

       // Else recur for right subarray
       return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
   }

   // If k is more than number of elements in array
   return INT_MAX;
}

int main() {
   int size, k;