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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
use rand::*;
use rayon::prelude::*;
#[allow(unused_assignments)]
pub fn bubble_sort(lst: & Vec<i32>) -> Vec<i32> {
let mut clean_pass = false;
let mut sorted: Vec<i32> = Vec::new();
sorted = lst.to_vec();
for i in 1..sorted.len() {
if clean_pass {
break;
} else {
clean_pass = true;
let mut j = 0;
while j < (sorted.len() - i) {
if sorted[j] > sorted[j + 1] {
sorted.swap(j, j+1);
clean_pass = false;
}
j+= 1;
}
}
}
sorted
}
pub fn merge_sort_par(lst: &Vec<i32>) -> Vec<i32> {
if lst.len() < 2 {
lst.to_vec();
}
let mid = (lst.len() + 1) /2;
let (left, right) = lst.split_at(mid);
let (left, right) = rayon::join(|| merge_sort(& left.to_vec()),
|| merge_sort(& right.to_vec()));
let halfsort = [left, right].concat();
let sorted = merge(& halfsort, mid);
sorted
}
pub fn merge_sort(lst: & Vec<i32>) -> Vec<i32> {
if lst.len() < 2 {
return lst.to_vec();
}
let mid = (lst.len() + 1) / 2;
let (left, right) = lst.split_at(mid);
let left = merge_sort(& left.to_vec());
let right = merge_sort(& right.to_vec());
let halfsort = [left, right].concat();
let sorted = merge(& halfsort, mid);
return sorted;
}
fn merge(lst: & Vec<i32>, mid: usize) -> Vec<i32> {
let size = lst.len();
let mut left_index = 0;
let mut right_index = mid;
let mut sorted: Vec<i32> = Vec::new();
for _i in 0..size {
if right_index >= size {
sorted.push(lst[left_index]);
left_index += 1;
} else if left_index >= mid {
sorted.push(lst[right_index]);
right_index += 1;
} else if lst[left_index] < lst[right_index] {
sorted.push(lst[left_index]);
left_index += 1;
} else {
sorted.push(lst[right_index]);
right_index += 1;
}
}
return sorted;
}
pub fn bogo_sort(lst: & Vec<i32>) -> Vec<i32> {
let mut sorted = Vec::new();
sorted.clone_from(lst);
while is_sorted(& sorted) == false {
shuffle(&mut sorted);
}
return sorted;
}
fn is_sorted(lst: & Vec<i32>) -> bool {
for i in 0..lst.len() - 1 {
if lst[i] > lst[i + 1] {
return false;
}
}
return true;
}
fn shuffle(lst: &mut Vec<i32>) {
let n = lst.len();
for i in 0..n {
lst.swap(i, thread_rng().gen::<usize>() % n);
}
}