Data structure algorithms

main.py

# Popular sort algorithms in Python

def bubble_sort(arr: list[int]) -> list[int]:
    for _ in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


def quick_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    median = arr[-1]
    smaller = [i for i in arr if i < median]
    larger = [i for i in arr if i > median]
    equal = [i for i in arr if i == median]
    return quick_sort(smaller) + equal + quick_sort(larger)


def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # merge lists
    i, j = 0, 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:]
    merged += right[j:]
    return merged

main.rs

// Binary search tree in Rust
use std::fmt::Debug;

struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

struct Tree<T> {
    root: Option<Box<Node<T>>>,
}

impl<T: PartialOrd + Debug> Tree<T> {
    fn new() -> Self {
        Self { root: None }
    }

    fn insert(&mut self, value: T) {
        self.root = Self::insert_recursive(self.root.take(), value);
    }

    fn insert_recursive(node: Option<Box<Node<T>>>, value: T) -> Option<Box<Node<T>>> {
        if let Some(mut current) = node {
            if value < current.value {
                current.left = Self::insert_recursive(current.left, value);
            } else {
                current.right = Self::insert_recursive(current.right, value);
            }
            Some(current)
        } else {
            Some(Box::new(Node {
                value,
                left: None,
                right: None,
            }))
        }
    }

    fn print(&self) {
        self.print_recursive(&self.root);
    }

    fn print_recursive(&self, node: &Option<Box<Node<T>>>) {
        if let Some(n) = node {
            self.print_recursive(&n.left);
            println!("{:?}", n.value);
            self.print_recursive(&n.right);
        }
    }
}

fn main() {
    let mut tree = Tree::new();
    
    let values = vec![5, 3, 7, 2, 4, 6, 8];
    for &value in &values {
        tree.insert(value);
    }

    println!("In-order traversal of the tree:");
    tree.print();
}

#[cfg(test)]
mod test {
    #[test]
    pub fn test_hello() {
        assert_eq!(1, 2)
    }
}