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

//! [Cycle sort](https://en.wikipedia.org/wiki/Cycle_sort)

use super::{Algorithm, Array};

/// [Cycle sort](https://en.wikipedia.org/wiki/Cycle_sort)
pub struct CycleSort;

impl Algorithm for CycleSort {
  fn sort(&self, array: Array) {
    let len = array.len();
    for cycle_start in 0..len - 1 {
      array.set_color(cycle_start, [0.0, 0.0, 1.0, 0.5]);

      let mut item = array.get(cycle_start);
      let mut sorted_index = self.find_sorted_index(&array, cycle_start, item);

      if sorted_index == cycle_start {
        continue;
      }

      while item == array.get(sorted_index) {
        sorted_index += 1;
      }

      let tmp = item;
      item = array.get(sorted_index);
      array.set(sorted_index, tmp);

      while sorted_index != cycle_start {
        array.set_color(sorted_index, [0.0, 0.0, 1.0, 0.5]);
        sorted_index = cycle_start;

        for i in cycle_start + 1..len {
          if array.get(i) < item {
            sorted_index += 1;
          }
          array.wait(2);
        }

        while item == array.get(sorted_index) {
          sorted_index += 1;
          array.wait(2);
        }

        let tmp = item;
        item = array.get(sorted_index);
        array.set(sorted_index, tmp);
      }
    }
  }

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

impl CycleSort {
  fn find_sorted_index(
    &self,
    array: &Array,
    cycle_start: usize,
    item: u32,
  ) -> usize {
    let len = array.len();

    let mut sorted_index = cycle_start;
    for i in cycle_start + 1..len {
      if array.get(i) < item {
        sorted_index += 1;
      }
      array.wait(2);
    }

    sorted_index
  }
}