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

//! [Quicksort](https://en.wikipedia.org/wiki/Quicksort)

use super::{Algorithm, Array};

/// [Quicksort](https://en.wikipedia.org/wiki/Quicksort)
pub struct Quicksort;

impl Algorithm for Quicksort {
  fn sort(&self, array: Array) {
    self.sort_slice(&array, 0, array.len() as isize - 1);
  }

  fn name(&self) -> String {
    "Quicksort".to_string()
  }
}

impl Quicksort {
  fn sort_slice(&self, array: &Array, low: isize, high: isize) {
    if low < high {
      let pivot = self.partition(array, low, high);

      for i in low..pivot {
        array.set_color(i as usize, [0.0, 1.0, 0.0, 0.3]);
      }
      array.set_color(pivot as usize, [1.0, 0.0, 0.0, 1.0]);
      for i in pivot + 1..=high {
        array.set_color(i as usize, [0.0, 0.0, 1.0, 0.3]);
      }

      self.sort_slice(array, low, pivot - 1);
      self.sort_slice(array, pivot + 1, high);

      for i in low..=high {
        array.reset_color(i as usize);
      }
    }
  }

  fn partition(&self, array: &Array, low: isize, high: isize) -> isize {
    let pivot = array.get(high as usize);
    let mut i = low;
    for j in low..high {
      if array.get(j as usize) <= pivot {
        array.swap(i as usize, j as usize);
        i += 1;
      }
      array.wait(15);
    }
    array.swap(i as usize, high as usize);
    i
  }
}