CODEWITHSUNDEEP
arraysalgorithmsortingdata-structuresquickselect
Sihal Fernando
Sihal Fernando

Reputation: 29

What's the most efficient way to find the k-th smallest element in an unsorted array?

I've read about the Quickselect algorithm, which has an average-case time complexity of O(n), but I'm not entirely sure how to implement it or if there are better alternatives.

Here's the problem in detail:

I'm given an unsorted array of integers: [12, 3, 5, 7, 19] I need to find the 3rd smallest element, which in this case is 7. Could someone explain how to implement Quickselect, or suggest another approach that might be more efficient for large arrays? Are there any edge cases or pitfalls I should be aware of?

Thanks in advance for your help!

I'm trying to find the k-th smallest element in an unsorted array, and I'm looking for the most efficient algorithm to do so. I know I could sort the array and then pick the k-th element, but that would take O(n log n) time, which seems inefficient for large datasets.

Upvotes: 2

Views: 67

Answers (1)

123
123

Reputation: 186

Here is an implementation of kth smallest element in an unsorted array (nums) using QuickSelect approach:

  • partition rearranges elements in the array such that elements smaller than the "pivot" (last element) are placed to its left, and larger ones to the right. It returns the index of the pivot after partitioning.

  • kth_smallest recursively uses partition to narrow down the search. Here we determine whether to search in the left or right subarray based on the pivot’s position relative to the k.

def kth_smallest(nums, k):
    if nums:
        pos = partition(nums, 0, len(nums) - 1)
        if k > pos + 1:
            return kth_smallest(nums[pos + 1:], k - pos - 1)
        elif k < pos + 1:
            return kth_smallest(nums[:pos], k)
        else:
            return nums[pos]


def partition(nums, left, right):
    res = left
    while left < right:
        if nums[left] < nums[right]:
            nums[left], nums[res] = nums[res], nums[left]
            res += 1
        left += 1
    nums[res], nums[right] = nums[right], nums[res]
    return res


print(kth_smallest([12, 3, 5, 7, 19], 3)) # 7
  • Average time complexity: O(N)

Upvotes: 1

Related Questions