Find K-th smallest element in an array

In many programming scenarios, it becomes necessary to find the K-th smallest element in an array. This problem can be solved using various algorithms, each with its own time complexity. In this blog post, we will explore the algorithms and provide implementations in C, C++, Python, and Java. Let’s dive in!

Algorithm:

1. Sorting Approach:

   • Sort the array in ascending order.
   • Return the K-th element from the sorted array.

   Time Complexity: O(n log n) (where n is the size of the array)

   • Sorting the array takes O(n log n) time using efficient sorting algorithms like Merge Sort or Quick Sort.
   • Accessing the K-th element from the sorted array takes constant time, O(1).

2. Min Heap Approach:

   • Create a Min Heap data structure.
   • Insert all the elements from the array into the Min Heap.
   • Extract the minimum element from the heap K times.

   Time Complexity: O(n + K log n) (where n is the size of the array)

   • Building the heap from the array takes O(n) time.
   • Extracting the minimum element K times takes O(K log n) time.
   • Overall, the time complexity is dominated by the heap operations.

Implementations:

1. C:

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int findKthSmallest(int arr[], int size, int k) {
    qsort(arr, size, sizeof(int), compare);
    return arr[k - 1];
}

int main() {
    int arr[] = { 3, 1, 5, 4, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    int kthSmallest = findKthSmallest(arr, size, k);
    printf("The %dth smallest element is: %dn", k, kthSmallest);

    return 0;
}

1. C++:

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = { 3, 1, 5, 4, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    std::sort(arr, arr + size);
    int kthSmallest = arr[k - 1];
    std::cout << "The " << k << "th smallest element is: " << kthSmallest << std::endl;

    return 0;
}

1. Python:

def find_kth_smallest(arr, k):
    arr.sort()
    return arr[k - 1]

arr = [3, 1, 5, 4, 2]
k = 3
kth_smallest = find_kth_smallest(arr, k)
print(f"The {k}th smallest element is: {kth_smallest}")

1. Java:

import java.util.Arrays;

public class KthSmallest {
    public static int findKthSmallest(int[] arr, int k) {
        Arrays.sort(arr);
        return arr[k - 1];
    }

    public static void main(String[] args) {
        int[] arr = { 3, 1, 5, 4, 2 };
        int k = 3;

        int kthSmallest = findKthSmallest(arr, k);
        System.out.println("The " + k + "th smallest element is: " + kthSmallest);
    }
}

Conclusion:
Finding the K-th smallest element in an array can be accomplished using various algorithms. The sorting approach provides a straightforward solution, but it has a higher time complexity of O(n log n). On the other hand, the Min Heap approach offers a more efficient solution with a time complexity of O(n + K log n). Implementations in C, C++, Python, and Java have been provided to demonstrate the algorithms. Remember to choose the appropriate approach based on the size of the array and the value of K to optimize the performance of your code.