algo 0.1.9

Algorithms & Data Structure implementations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

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

pub fn sort_with_copy<T: PartialOrd + Copy>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let key = arr[i];
        let mut j = i - 1;

        while arr[j] > key {
            arr.swap(j + 1, j);

            if j == 0 {
                break;
            }

            j = j - 1;
        }

        arr[j + 1] = key;
    }
}

pub fn sort_with_binary_search<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        match arr[0..i].binary_search(&arr[i]) {
            Ok(_) => continue,
            Err(idx) => {
                for j in 0..(i - idx) {
                    arr.swap(i - j, i - j - 1);
                }
            }
        }
    }
}

#[test]
fn test_sort_simple() {
    let mut arr = [-5, 4, 1, -3, 2];

    sort(&mut arr);

    assert!(arr == [-5, -3, 1, 2, 4]);
}

#[test]
fn test_sort_with_copy() {
    let mut arr = [-5, 4, 1, -3, 2];

    sort_with_copy(&mut arr);

    assert!(arr == [-5, -3, 1, 2, 4]);
}

#[test]
fn test_sort_with_binary_search() {
    let mut arr = [-5, 4, 1, -3, 2];

    sort_with_binary_search(&mut arr);

    assert!(arr == [-5, -3, 1, 2, 4]);
}

#[bench]
fn bench_sort_simple(b: &mut ::test::Bencher) {
    b.iter(|| {
        let mut arr: Vec<u32> = (0..1000).rev().collect();

        sort(&mut arr);
    })
}

#[bench]
fn bench_sort_with_copy(b: &mut ::test::Bencher) {
    b.iter(|| {
        let mut arr: Vec<u32> = (0..1000).rev().collect();

        sort_with_copy(&mut arr);
    })
}

#[bench]
fn bench_sort_with_binary_search(b: &mut ::test::Bencher) {
    b.iter(|| {
        let mut arr: Vec<u32> = (0..1000).rev().collect();

        sort_with_binary_search(&mut arr);
    })
}