Python If you play well , Not only can it improve work efficiency , You can also make some interesting things , such as Make animations and generate videos . I once realized a Generate visual video of sorting algorithm Script for , And open source GitHub. Before the introduction , Recommend a learning resource , If you are right about Python Very interested and want to enhance practical skills , You can experience . （https://jq.qq.com/?_wv=1027&k=UEbz4NcQ）
All say Python It's glue language , call C/C++ The module is very convenient , So its wide range of uses is largely due to C/C++ The ecology of . For this personal project , The steps to generate the video use the famous C library FFMpeg,Python The nature of glue language makes it possible .
use Matplotlib Library to achieve sorting algorithm animation , And make use of FFMpeg Generate mp4 raw materials , Last use Premiere After the manual post-processing . In the video, nine sorting algorithms are put together for comparison , Namely ：
Insertion sort Shell Sort Selection sort
Merge sort Quick sort Heap sort
Bubble sort Comb sort Monkey order
( Monkey sorting is all about skin , After all, the only chance of success is 1/64）
When you come up with a plan , I inevitably took a road from bend to straight . The original plan is , use Python Simulation of various sorting algorithms , Then draw the step picture frame by frame , Import the image sequence into AE Turn it into a video . Later I thought python It's too much trouble to write pictures directly , There are no more convenient wheels ？ So I thought of Matplotlib Library can be used as a chart tool to draw histogram , It just coincides with the image form I want . Later it was changed to use Python+Matplotlib Frame by frame , Then import the image sequence into AE Turn it into a video . Last , I think the image sequence import AE too troublesome , Can I output video directly ？ Fortunately Matplotlib It supports frame by frame animation , You can talk to FFMpeg combination , Directly to mp4 Format will output the animation .excited！
As for how to get the slice of the sorting algorithm at each time , I've thought about linking frame numbers to the progress of sorting algorithms , Get the next frame data while playing . Later I found it difficult to operate , You can go through the sorting algorithm first , Get the data for all frames , And play it frame by frame . Although this consumes a little more memory , It's still very simple to realize . Let's take the basic selection sorting as an example ：
def selection_sort(data_set):
ds = copy.deepcopy(data_set)
for i in range(0, Data.data_count-1):
for j in range(i+1, Data.data_count):
if ds[j].value < ds[i].value:
ds[i], ds[j] = ds[j], ds[i]
return ds
The code for sorting is very simple , What we have to do is to intercept the data slice as the frame data in the representative place of the algorithm , And then process frame data at the same time , Coloring for some important numerical values . The final code is like this ： （https://jq.qq.com/?_wv=1027&k=UEbz4NcQ）
def selection_sort(data_set):
# FRAME OPERATION BEGIN
frames = [data_set]
# FRAME OPERATION END
ds = copy.deepcopy(data_set)
for i in range(0, Data.data_count-1):
for j in range(i+1, Data.data_count):
# FRAME OPERATION BEGIN
ds_r = copy.deepcopy(ds)
frames.append(ds_r)
ds_r[i].set_color('r')
ds_r[j].set_color('k')
# FRAME OPERATION END
if ds[j].value < ds[i].value:
ds[i], ds[j] = ds[j], ds[i]
# FRAME OPERATION BEGIN
frames.append(ds)
return frames
# FRAME OPERATION END
You can see that the new code adds three blocks to the original code to process the frame data , And mark it with a comment . First block ： Initialize frame list , Raw data as the first frame ; Second pieces ： Capture frames inside the second layer loop , And put the i Data are painted red （r）, The first j Data black （k）; Third pieces ： Add sorted data to the frame list as the last frame , And return to the frame list .
such , We can see in the most intuitive way the selection and sorting process and i and j The meaning of ： The first i Elements have been taking j The minimum value of the swept part .
Select sort visualization of course , This is just a simple interception and coloring scheme in these sorting algorithms . Some algorithms are more abstract , It's hard to see the law from the sorting process , For example, heap sort . I painted each layer of the big root pile with different colors , And use red to indicate the node that is sinking or floating , Use black to indicate the child node or parent node that needs to be compared in the process of adjusting the position of the red node . Now the sorting process is more intuitive ： （https://jq.qq.com/?_wv=1027&k=UEbz4NcQ）
as for Matplotlib The drawing and animation part of , You can check the official website documents , I won't go into that here . And the use of FFMpeg The library exports animation to mp4 Specific practices of documents , This article is very good ：matplotlib animation Save animation (save function ) Detailed explanation .
I've made all this code open source , And optimized the user interface , There are several outputs ：
For details, please refer to README Document usage .GitHub Warehouse address ：zamhown/sorting-visualizergithub.com/zamhown/sorting-visualizer
Ashamed to speak , This is what I wrote README The most serious one …… welcome star、fork Or to mention issue.
If you want to improve or add a new sorting algorithm, you are welcome to submit pr.
