SORT ALGORITHMS
Obs:. This just a briefing of the algorithm!!!
SELECTION SORT
Selection Sort is an algorithm that use order by selection.
Worst, Medium and Best Case Complexity:
O(n²)
https://en.wikipedia.org/wiki/Selection_sort
extern crate sort_algorithms;
use sort_algorithms::selection_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
selection_sort(&mut arr, |a, b| a < b);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
BUBBLE SORT
Bubble sort is an algorithm that use order by comapare values.
Worst, Medium Case Complexity:
O(n²)
Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Bubble_sort
extern crate sort_algorithms;
use sort_algorithms::bubble_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
bubble_sort(&mut arr, |a, b| a < b);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
QUICK SORT
Quick sort is an algorithm that use strategy divide to conquer.
Worst Case Complexity:
O(n²)
Medium Case Complexity:
O(n)
Best Case Complexity:
O(n log n)
https://en.wikipedia.org/wiki/Quicksort
extern crate sort_algorithms;
use sort_algorithms::quick_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
quick_sort(&mut arr, |a, b| a < b);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
HEAP SORT
Heap sort is an generalist algorithm that use the strategy order by selecion.
Worst Case Complexity:
O(n log n)
Medium Case Complexity:
O(n log n)
Best Case Complexity:
O(n log n)
https://en.wikipedia.org/wiki/Heapsort
extern crate sort_algorithms;
use sort_algorithms::heapsort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
heapsort(&mut arr);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
MERGE SORT
Merge sort is an algorithm that use the strategy order by comparation and divide to conquer.
Worst Case Complexity:
O(n log n)
Medium Case Complexity:
O(n log n)
Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Merge_sort
extern crate sort_algorithms;
use sort_algorithms::merge_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
merge_sort(&mut arr, |a, b| a < b);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
RADIX SORT
Radix sort is an algorithm that use the strategy non-comparative.
Worst Case Complexity:
O(n)
Medium Case Complexity:
O(n)
Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Radix_sort
Can only be used to sort lists of positive integers as key
extern crate sort_algorithms;
use sort_algorithms::radix_sort;
fn main() {
let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
radix_sort(&mut arr, |&a| a);
println!("{:?}", &arr);
assert_eq!(arr, [ 0, 1, 2, 3, 4, 5, 6, 7]);
}
INSERTION SORT
Insertion sort is an algorithm that use strategy where catch one element and compare against orthers.
Worst, Medium Case Complexity:
O(n²)
Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Insertion_sort
extern crate sort_algorithms;
use sort_algorithms::insertion_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
insertion_sort(&mut arr, |a, b| a < b);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
COCKTAIL SHAKER SORT
Cocktail Shaker Sort is an algorithm is a derivation from bubble sort.
Worst, Medium Case Complexity:
O(n²)
Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Cocktail_shaker_sort
extern crate sort_algorithms;
use sort_algorithms::cocktail_shaker_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
cocktail_shaker_sort(&mut arr, |a, b| a < b);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}
GRAVITY SORT / BEAD SORT
Gravity Sort is an algorithm that use the strategy of
Natural Sorting.
Worst, Medium and Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Bead_sort
Can only be used to sort lists of positive integers as key
extern crate sort_algorithms;
use sort_algorithms::gravity_sort;
fn main() {
let mut arr = vec![9, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
gravity_sort(&mut arr, |&a| a);
println!("{:?}", &arr);
assert_eq!(arr, [ 0, 1, 2, 3, 4, 5, 6, 9]);
}
COUNTING SORT
Counting Sort is an algorithm that use the strategy of it uses key values as indexes into an array and
the
Ω(n log n) lower bound for comparison sorting will not apply.
Worst, Medium and Best Case Complexity:
O(n)
https://en.wikipedia.org/wiki/Counting_sort
Can only be used to sort lists of positive integers as key
extern crate sort_algorithms;
use sort_algorithms::counting_sort;
fn main() {
let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
counting_sort(&mut arr, |&a| a);
println!("{:?}", &arr);
assert_eq!(arr, [0, 1, 2, 3, 4, 5, 6, 7]);
}
FLASH SORT
Flash Sort is an algorithm that use the strategy that you can compute the approximate final position directly from the element value,
with no comparisons.
Worst, Medium and Best Case Complexity:
O(n)
http://www.neubert.net/Flapaper/9802n.htm
extern crate sort_algorithms;
use sort_algorithms::flash_sort;
fn main() {
let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
println!("{:?}", &arr);
flash_sort(&mut arr, |&a| a);
println!("{:?}", &arr);
assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}