find the kth smallest element in an array in rust

To find the kth smallest element in an array, we can use the quickselect algorithm which is a variation of the quicksort algorithm. The quickselect algorithm has an average time complexity of O(n) and a worst case time complexity of O(n^2).


main.rs
use rand::{thread_rng, Rng};

// swap two elements in the array
fn swap(arr: &mut [i32], i: usize, j: usize) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// partition function for quickselect
fn partition(arr: &mut [i32], left: usize, right: usize) -> usize {
    let pivot_index = thread_rng().gen_range(left, right + 1); 
    let pivot_value = arr[pivot_index]; 
    swap(arr, pivot_index, right);
    let mut store_index = left;
    for i in left..right {
        if arr[i] < pivot_value {
            swap(arr, i, store_index);
            store_index += 1;
        }
    }
    swap(arr, store_index, right);
    store_index
}

// quickselect function to find kth smallest element
fn quickselect(arr: &mut [i32], left: usize, right: usize, k: usize) -> i32 {
    if left == right {
        return arr[left];
    }
    let pivot_index = partition(arr, left, right);
    if k == pivot_index {
        return arr[k];
    } else if k < pivot_index {
        return quickselect(arr, left, pivot_index - 1, k);
    } else {
        return quickselect(arr, pivot_index + 1, right, k);
    }
}

// main function
fn main() {
    let mut arr: [i32; 10] = [9, 1, 4, 7, 6, 8, 2, 5, 10, 3];
    let k = 4; // find 4th smallest element in array
    let result = quickselect(&mut arr, 0, arr.len() - 1, k - 1);
    println!("{}th smallest element in array is {}", k, result);
}
1390 chars
48 lines

In the above code, the quickselect function takes an array, left and right indices, and the kth smallest element to be found as input arguments.

We first select a pivot element and partition the array around the pivot such that elements less than the pivot are on the left and elements greater than the pivot are on the right.

If the index of the pivot element is equal to k, we have found the kth smallest element and return it.

If the index of the pivot element is greater than k, we recursively call the quickselect function on the left subarray, otherwise we recursively call it on right subarray.

The main function initializes an array and calls the quickselect function to find the kth smallest element in the array.

similar rust code snippets

find the kth smallest element in an array in rust

find the kth largest element in an array in rust

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

remove an element from the middle of an array in rust

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

find the index of an element in an array in rust

remove an element from the beginning of an array in rust

sort an array in rust

add an element to the beginning of an array in rust

add an element to the end of an array in rust

related categories