pub fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
    let n = arr.len();
    for i in 0..n {
        for j in 1..(n-i) {
            if arr[j-1] > arr[j] {
                arr.swap(j-1, j);
            }
        }
    }
}

pub fn shell_sort<T: PartialOrd>(arr: &mut [T]) {
    let n = arr.len();
    let mut h = 1;
    while h < n / 3 {
        h = 3 * h + 1;
    }
    while h >= 1 {
        for i in h..n {
            let mut j = i;
            while j >= h && arr[j] < arr[j - h] {
                arr.swap(j, j - h);
                j -= h;
            }
        }
        h /= 3;
    }
}

pub fn heap_sort<T: PartialOrd>(arr: &mut [T]) {
    let n = arr.len();

    for i in (0..n / 2).rev() {
        heapify(arr, n , i);
    }

    for i in (1..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn heapify<T: PartialOrd>(arr: &mut [T], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if left < n && arr[left] > arr[largest] {
        largest = left;
    }

    if right < n && arr[right] > arr[largest] {
        largest = right;
    }
    if largest != i {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::Rng;

    #[test]
    fn test_bubble_sort() {
        let mut rng = rand::thread_rng();
        let arr= [0; 100000];
        let mut arr = arr.map(|_| rng.gen_range(0..1000));
        assert_eq!(arr.sort(), bubble_sort(&mut arr))
    }

    #[test]
    fn test_shell_sort() {
        let mut rng = rand::thread_rng();
        let arr= [0; 100000];
        let mut arr = arr.map(|_| rng.gen_range(0..1000));
        assert_eq!(arr.sort(), shell_sort(&mut arr))
    }

    #[test]
    fn test_heap_sort() {
        let mut rng = rand::thread_rng();
        let arr= [0; 100000];
        let mut arr = arr.map(|_| rng.gen_range(0..1000));
        let mut lettere = ['b' , 'a', 'c'];
        assert_eq!(arr.sort(), heap_sort(&mut arr));
        assert_eq!(lettere.sort(), heap_sort(&mut lettere))
    }
}