SHARE
TWEET

Untitled

a guest Jun 17th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. fn main() {
  2.     let mut array = vec![true, false, false, false];//43, 97, 45, 54, 91, 16, 76, 18, 88, 89, 87, 5, 66, 29, 61, 8, 85, 30, 81, 89, 89, 43, 67, 7, 50, 23, 48, 83, 88, 36, 80, 76, 85, 4, 83, 30, 68, 66, 65, 5, 18, 6, 88, 1, 17, 4, 23, 40, 70, 41];
  3.     sort(&mut array[..]);
  4.     println!("{:?}", array);
  5. }
  6.  
  7. fn sort3<T : PartialOrd>(array : &mut [T]) {
  8.     let n = array.len();
  9.     assert!(n <= 3);
  10.  
  11.     if n <= 1 {
  12.         return;
  13.     }
  14.  
  15.     if array[0] > array[1] {
  16.         array.swap(0, 1);
  17.     }
  18.  
  19.     if n == 2 {
  20.         return;
  21.     }
  22.  
  23.     if array[1] > array[2] {
  24.         array.swap(1, 2);
  25.     }
  26.  
  27.     if array[0] > array[1] {
  28.         array.swap(0, 1);
  29.     }
  30. }
  31.  
  32. fn merge<T : PartialOrd>(left : &mut [T], right : &mut [T]) {
  33.     let left_len = left.len();
  34.     let right_len = right.len();
  35.     let mut vec = Vec::with_capacity(left_len + right_len);
  36.     let mut i = 0;
  37.     let mut j = 0;
  38.  
  39.     while i < left_len && j < right_len {
  40.         if left[i] < right[j] {
  41.             let next = std::mem::replace(&mut left[i], unsafe { std::mem::uninitialized() });
  42.             vec.push(next);
  43.             i += 1;
  44.         } else {
  45.             let next = std::mem::replace(&mut right[j], unsafe { std::mem::uninitialized() });
  46.             vec.push(next);
  47.             j += 1;
  48.         }
  49.     }
  50.  
  51.     while i < left_len {
  52.         let next = std::mem::replace(&mut left[i], unsafe { std::mem::uninitialized() });
  53.         vec.push(next);
  54.         i += 1;
  55.     }
  56.  
  57.     while j < right_len {
  58.         let next = std::mem::replace(&mut right[j], unsafe { std::mem::uninitialized() });
  59.         vec.push(next);
  60.         j += 1;
  61.     }
  62.  
  63.     let mut k = 0;
  64.     for item in vec {
  65.         if k < left_len {
  66.             unsafe { std::ptr::write(&mut left[k], item); }
  67.         } else {
  68.             unsafe { std::ptr::write(&mut right[k - left_len], item); }
  69.         }
  70.  
  71.         k += 1;
  72.     }
  73. }
  74.  
  75. fn sort<T : PartialOrd>(array : &mut [T]) {
  76.     let n = array.len();
  77.     if n <= 3 {
  78.         sort3(array);
  79.     } else {
  80.         let (left, right) = array.split_at_mut(n / 2);
  81.         sort(left);
  82.         sort(right);
  83.         merge(left, right);
  84.     }
  85. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top