This article is from the Python and Algorithm Community by ZGLG
1. The charm of algorithms
Deep research sorting algorithm is a kind of method of introduction to algorithms is relatively good remember four years ago and now manually to realize common eight kinds of sort algorithm, through the randomly generated some data, one by one check code implementation whether the sorting process is consistent with the expected, more do more exciting, more exciting more want to go to study, on the bus, eat on the way… Those images are still fresh in my mind.
Ability is limited, there was no animation generating sorting process, so the years thinking about time must have the process of sorting is made into the movie, and then share out, let more friends see, through the dynamic demonstration animation sorting algorithm, find the real pleasure of learning algorithm, thus moving towards a new cognitive domain.
I was writing in C++ at the time, but Python has grown rapidly. Thanks to Python’s simplicity and easy-to-use interfaces, someone has recently opened a project on github that uses Python animations to show sorting algorithms.
Animations are made using Matplotlib, which is even more perfect, as you can learn the perfect algorithm and improve your Python proficiency while also learning how to animate using Matplotlib.
Perfect answer
The library demonstrates eight common sorting algorithms:
bubble-sort: Only show the visualization of bubble sorting algorithm in the animation. The following arguments have similar functions.comb-sortheap-sortinsertion-sortmerge-sortquick-sortselection-sortshell-sort
The script that starts is output.py, and there are three types of arguments to the script, which are explained below.
python output.py play heap-sort reversed
Copy the codePlay shows the sorted animations with two other options: save HTML and MP4
play: Play an animation of a specific sorting algorithm or all algorithms in a new window, as a “figure” to Matplotlib.save-html: Save the animation as a HTML page with a sequence of images.save-mp4: Save the animation as a MP4 video.
Heap-sort indicates heap sort, which is the animation display of the sorting algorithm you want to see in this script execution. Quick-sort indicates the animation display of the quicksort, and all indicates the animation display of all sorting algorithms at once.
The reversed type of argument is what I want to focus on, and there are several other options for this type of argument. It is usually said that the average time complexity of a fast sort is nlog2n. Why is it average?
It is hard to find a real t 100% accurate function, input data, through the t (data) to calculate the accurate theory of execution time, because the distribution of the data can’t accurate fitting out, and it directly affect the actual sort time, such as input a sort good sequence, almost without a repeating element sequence of a random sequence, A decreasing sequence. So you can only give a rough estimate of execution time based on some kind of distribution.
almost-sorted: Sort an almost-sorted sequence.few-unique: Sort a few-unique sequence.random(default) : Sort a random sequence.reversed: Sort a descending sequence.
3 Animation Display
The module and example code used are as follows: \
The package used is mainly the built-in module random, OS, SYS, RE, and animation function of Matplotlib. The rest is the manual implementation of 8 sorting algorithms.
import random
import os
import sys
import re
from matplotlib import pyplot as plt
from matplotlib import animation
from sorting.data import Data
from sorting.selectionsort import selection_sort
from sorting.bubblesort import bubble_sort
from sorting.insertionsort import insertion_sort
from sorting.shellsort import shell_sort
from sorting.mergesort import merge_sort
from sorting.quicksort import quick_sort
from sorting.heapsort import heap_sort
from sorting.combsort import comb_sort
from sorting.monkeysort import monkey_sort
Copy the codeQuicksort code, which saves all action frames:
# Script Name : quicksort.py
# Author : Howard Zhang
# Created : 14th June 2018
# Last Modified : 14th June 2018
# Version : 1.0
# Modifications :
# Description : Quick sorting algorithm.
import copy
from .data import Data
def quick_sort(data_set):
# FRAME OPERATION BEGIN
frames = [data_set]
# FRAME OPERATION END
ds = copy.deepcopy(data_set)
qsort(ds, 0, Data.data_count, frames)
# FRAME OPERATION BEGIN
frames.append(ds)
return frames
# FRAME OPERATION END
def qsort(ds, head, tail, frames):
if tail - head > 1:
# FRAME OPERATION BEGIN
ds_y = copy.deepcopy(ds)
for i in range(head, tail):
ds_y[i].set_color('y')
# FRAME OPERATION END
i = head
j = tail - 1
pivot = ds[j].value
while i < j:
# FRAME OPERATION BEGIN
frames.append(copy.deepcopy(ds_y))
frames[- 1][i if ds[i].value == pivot else j].set_color('r')
frames[- 1][j if ds[i].value == pivot else i].set_color('k')
# FRAME OPERATION END
if ds[i].value > pivot or ds[j].value < pivot:
ds[i], ds[j] = ds[j], ds[i]
# FRAME OPERATION BEGIN
ds_y[i], ds_y[j] = ds_y[j], ds_y[i]
frames.append(copy.deepcopy(ds_y))
frames[- 1][i if ds[i].value == pivot else j].set_color('r')
frames[- 1][j if ds[i].value == pivot else i].set_color('k')
# FRAME OPERATION END
if ds[i].value == pivot:
j -= 1
else:
i += 1
qsort(ds, head, i, frames)
qsort(ds, i+1, tail, frames)
Copy the codeI have executed 8 sorting algorithms and recorded 3 animations that look like this:
1) Quicksort
2) merge sort \
3) Heap sort \
Project address, which has the complete source code:
Github.com/zamhown/sor…
Note: the menu of the official account includes an AI cheat sheet, which is very suitable for learning on the commute.
Machine learning Online Manual Deep Learning online Manual AI Basic Download (Part 1)4500+ user ID:92416895), please reply to knowledge PlanetCopy the codeLike articles, click Looking at the
