find the kth smallest element in an array in go

Here's an implementation of finding the kth smallest element in an array using QuickSelect algorithm in Go:


main.go
package main

import "fmt"

func partition(nums []int, left int, right int, pivot int) int {
    pivotValue := nums[pivot]
    nums[pivot], nums[right] = nums[right], nums[pivot]
    storeIndex := left
    for i := left; i < right; i++ {
        if nums[i] < pivotValue {
            nums[i], nums[storeIndex] = nums[storeIndex], nums[i]
            storeIndex++
        }
    }
    nums[storeIndex], nums[right] = nums[right], nums[storeIndex]
    return storeIndex
}

func quickSelect(nums []int, left int, right int, k int) int {
    if left == right {
        return nums[left]
    }
    pivotIndex := left + (right-left)/2
    pivotIndex = partition(nums, left, right, pivotIndex)
    if k == pivotIndex {
        return nums[k]
    } else if k < pivotIndex {
        return quickSelect(nums, left, pivotIndex-1, k)
    }
    return quickSelect(nums, pivotIndex+1, right, k)
}

func kthSmallestElement(nums []int, k int) int {
    return quickSelect(nums, 0, len(nums)-1, k-1)
}

func main() {
    arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3}
    k := 7
    fmt.Printf("The %dth smallest element in %v is %d\n", k, arr, kthSmallestElement(arr, k))
}
1153 chars
42 lines

In this code, partition() function is used to rearrange the elements in the array around a pivot value such that elements less than the pivot value are moved to the left side of the pivot, and elements greater than or equal to the pivot value are moved to the right side of the pivot. The quickSelect() function recursively selects a pivot until the kth smallest element is found. Finally, kthSmallestElement() calls the quickSelect() function with appropriate parameters.

The output of the above code with arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3} and k := 7 will be:


main.go
The 7th smallest element in [3 1 4 1 5 9 2 6 5 3] is 5
55 chars
2 lines

similar go code snippets

find the kth smallest element in an array in go

find the kth largest element in an array in go

sort an array in go

insert an element into an array at a specific index in go

find the index of an element in an array in go

remove an element from the middle of an array in go

add an element to the beginning of an array in go

remove an element from an array at a specific index in go

remove an element from the beginning of an array in go

add an element to the end of an array in go

related categories