| 1 | from manim_imports_ext import * |
| 2 | |
| 3 | class QuickSort(AlgoScene): |
| 4 | def __init__(self, **kwargs): |
| 5 | super().__init__(**kwargs) |
| 6 | self.partition_time = 0 |
| 7 | self.low_arrow = None |
| 8 | self.current_arrow = None |
| 9 | random.seed(1) |
| 10 | |
| 11 | def scale(self, s): |
| 12 | self.camera.frame.set_width(self.camera.frame.get_width()/s) |
| 13 | self.camera.frame.set_height(self.camera.frame.get_height()/s) |
| 14 | |
| 15 | def add_span(self, arr, low, high): |
| 16 | l = arr.submobjects[low].get_bounding_box_point(DOWN) |
| 17 | h = arr.submobjects[high].get_bounding_box_point(DOWN) |
| 18 | color = self.rand_color() |
| 19 | span = Line(l, h, color=color) |
| 20 | delta = DOWN*self.partition_time*0.3 |
| 21 | span.shift(delta) |
| 22 | span_left = Line(l, l+delta, color=color) |
| 23 | span_right = Line(h, h+delta, color=color) |
| 24 | self.play(ShowCreation(span), ShowCreation(span_left), ShowCreation(span_right)) |
| 25 | self.wait() |
| 26 | |
| 27 | def compare(self, arr, a, b): |
| 28 | ca = arr.submobjects[a].copy() |
| 29 | cb = arr.submobjects[b].copy() |
| 30 | self.play(ApplyMethod(ca.move_to, ORIGIN+DOWN/2+LEFT), |
| 31 | ApplyMethod(cb.move_to, ORIGIN+DOWN/2+RIGHT)) |
| 32 | t = None |
| 33 | m = None |
| 34 | if arr.get(a) > arr.get(b): |
| 35 | t = Text(">", color=YELLOW).scale(0.5) |
| 36 | m = self.create_serif_font("不需要移动").scale(0.5) |
| 37 | else: |
| 38 | t = Text("<=", color=YELLOW).scale(0.5) |
| 39 | m = self.create_serif_font("交换放左边").scale(0.5) |
| 40 | t.shift(DOWN/2) |
| 41 | m.next_to(cb) |
| 42 | self.add(t, m) |
| 43 | self.play(ShowCreation(m)) |
| 44 | self.wait(1) |
| 45 | self.play(FadeOut(ca, run_time=0.2), FadeOut(cb, run_time=0.2), FadeOut(t, run_time=0.2), FadeOut(m, run_time=0.2)) |
| 46 | |
| 47 | def partition(self, arr, low, high): |
| 48 | self.partition_time += 1 |
| 49 | # 增加一条横线 |
| 50 | self.add_span(arr, low, high) |
| 51 | anchor = arr.get(high) |
| 52 | # 高亮锚点 |
| 53 | self.play(ApplyMethod(arr.submobjects[high].set_color, BLUE)) |
| 54 | i = low - 1 |
| 55 | arr.move_arrow(self.low_arrow, low) |
| 56 | |
| 57 | for j in range(low, high): |
| 58 | arr.move_arrow(self.current_arrow, j) |
| 59 | self.compare(arr, j, high) |
| 60 | if arr.get(j) <= anchor: |
nothing calls this directly
no outgoing calls
no test coverage detected