fn bubble_sort < T : Ord + Copy > ( mut list : Vec < T > ) -> Vec < T > {
for i in 0 .. list. len ( ) {
for j in i .. list. len ( ) {
if list[ i] > list[ j] {
list. swap ( i, j) ;
}
}
}
return list;
}
fn merge_sort < T : Ord + Copy > ( list : Vec < T > ) -> Vec < T > {
if list. len ( ) > 1 {
let middle = list. len ( ) / 2 ;
let l = merge_sort ( list[ ..middle] . to_vec ( ) ) ;
let r = merge_sort ( list[ middle..] . to_vec ( ) ) ;
return merge ( l, r)
}
return list
}
fn merge < T : Ord + Copy > ( mut l : Vec < T > , mut r : Vec < T > ) -> Vec < T > {
let mut new_vec = vec ! [ ] ;
while l. len ( ) > 0 && r. len ( ) > 0 {
if l[ 0 ] < r[ 0 ] {
new_vec. push ( l. remove ( 0 ) ) ;
} else {
new_vec. push ( r. remove ( 0 ) ) ;
}
}
new_vec. append ( & mut l) ;
new_vec. append ( & mut r) ;
return new_vec;
}
Quicksort (Hoare partition scheme)
fn quicksort < T : Ord + Copy > ( vector : & mut [ T ] ) -> & [ T ] {
if vector. len ( ) > 1 {
let p = partition ( vector) ;
quicksort ( & mut vector[ ..p] ) ;
quicksort ( & mut vector[ p..] ) ;
}
return vector;
}
fn partition < T : Ord + Copy > ( vector : & mut [ T ] ) -> usize {
let ( mut left, mut right) = ( 0 , vector. len ( ) -1 ) ;
let pivot = vector[ vector. len ( ) / 2 ] ;
loop {
while vector[ left] < pivot {
left+=1 ;
}
while vector[ right] > pivot {
right-=1 ;
}
if left >= right {
break ;
}
vector. swap ( left, right)
}
return right
}