使用Python可視化展示排序算法

更新時(shí)間：2024年11月25日 08:30:41 作者：關(guān)山月

這篇文章主要介紹了使用Python可視化展示排序算法,讓我們創(chuàng)建一個(gè)名為algorithm?.py的文件,在這個(gè)文件中,我們將用python編寫所有的排序算法,需要的朋友可以參考下

算法

讓我們創(chuàng)建一個(gè)名為algorithm .py的文件，在這個(gè)文件中，我們將用python編寫所有的排序算法。導(dǎo)入時(shí)間模塊，告知用戶可視化工具所花費(fèi)的時(shí)間。

創(chuàng)建一個(gè)名為Algorithm的類，并將這段代碼粘貼到其中：

class Algorithm:
    def __init__(self, name):
        self.array = random.sample(range(512), 512) # Random array of size 512
        self.name = name # Get name of the variable

    def update_display(self, swap1=None, swap2=None):
        import visualizer
        visualizer.update(self, swap1, swap2) # pass the indexes to be swapped into the visualizer

    def run(self): # Start the timer and run the algorithm
        self.start_time = time.time() 
        self.algorithm()
        time_elapsed = time.time() - self.start_time
        return self.array, time_elapsed

我們將首先創(chuàng)建一個(gè)大小為512的隨機(jī)數(shù)組。在update_display方法中，我們將調(diào)用visualizer.py中的更新函數(shù)，稍后我們將編寫該函數(shù)來處理圖形。最后，run方法將啟動(dòng)計(jì)時(shí)器并調(diào)用算法函數(shù)。

Selection Sort選擇排序

class SelectionSort(Algorithm):
    def __init__(self):
        super().__init__("SelectionSort")

    def algorithm(self):
        for i in range(len(self.array)):
            min_idx = i
            for j in range(i+1, len(self.array)):
                if self.array[j] < self.array[min_idx]:
                    min_idx = j
            self.array[i], self.array[min_idx] = self.array[min_idx], self.array[i]
            self.update_display(self.array[i], self.array[min_idx])

SelectionSort類將繼承Algorithm類，并在其中實(shí)現(xiàn)選擇排序。每當(dāng)數(shù)組更新時(shí)，我們調(diào)用update_display方法并實(shí)時(shí)呈現(xiàn)數(shù)組的排序。類似地，我們對(duì)其他算法也同樣實(shí)現(xiàn)。

Bubble Sort冒泡排序

class BubbleSort(Algorithm):
    def __init__(self):
        super().__init__("BubbleSort")

    def algorithm(self):
        for i in range(len(self.array)):
            for j in range(len(self.array)-1-i):
                if self.array[j] > self.array[j+1]:
                    self.array[j], self.array[j+1] = self.array[j+1], self.array[j]
            self.update_display(self.array[j], self.array[j+1])

Insertion Sort插入排序

class InsertionSort(Algorithm):
    def __init__(self):
        super().__init__("InsertionSort")

    def algorithm(self):
        for i in range(len(self.array)):
            cursor = self.array[i]
            idx = i
            while idx > 0 and self.array[idx-1] > cursor:
                self.array[idx] = self.array[idx-1]
                idx -= 1
            self.array[idx] = cursor
            self.update_display(self.array[idx], self.array[i])

Merge Sort歸并排序

class MergeSort(Algorithm):
    def __init__(self):
        super().__init__("MergeSort")

    def algorithm(self, array=[]):
        if array == []:
            array = self.array
        if len(array) < 2:
            return array
        mid = len(array) // 2
        left = self.algorithm(array[:mid])
        right = self.algorithm(array[mid:])
        return self.merge(left, right)

    def merge(self, left, right):
        result = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
            self.update_display()
        result += left[i:]
        result += right[j:]
        self.array = result
        self.update_display()
        return result

Quick Sort快速排序

class QuickSort(Algorithm):
    def __init__(self):
        super().__init__("QuickSort")

    def algorithm(self, array=[], start=0, end=0):
        if array == []:
            array = self.array
            end = len(array) - 1
        if start < end:
            pivot = self.partition(array,start,end)
            self.algorithm(array,start,pivot-1)
            self.algorithm(array,pivot+1,end)

    def partition(self, array, start, end):
        x = array[end]
        i = start-1
        for j in range(start, end+1, 1):
            if array[j] <= x:
                i += 1
                if i < j:
                    array[i], array[j] = array[j], array[i]
                    self.update_display(array[i], array[j])
        return i

可視化

恭喜你!你剛剛寫了所有流行的排序算法。最后一步是可視化地顯示這些排序算法。

下面是visualizer.py文件的代碼。

import algorithms
import time
import os
import sys
import pygame

 # Set the window length and breadth  (Make sure that the breadth is equal to size of array. [512])
dimensions = [1024, 512]
# List all the algorithms available in the project in dictionary and call the necessary functions from algorithms.py
algorithms = {"SelectionSort": algorithms.SelectionSort(), "BubbleSort": algorithms.BubbleSort(), "InsertionSort": algorithms.InsertionSort(), "MergeSort": algorithms.MergeSort(), "QuickSort": algorithms.QuickSort()}

# Check list of all the available sorting techniques using 'list'
if len(sys.argv) > 1:
    if sys.argv[1] == "list":
        for key in algorithms.keys(): print(key, end=" ") # Display the available algorithms
        print("")
        sys.exit(0)

# Initalise the pygame library
pygame.init()
# Set the dimensions of the window and display it
display = pygame.display.set_mode((dimensions[0], dimensions[1]))
# Fill the window with purple hue
display.fill(pygame.Color("#a48be0"))

def check_events(): # Check if the pygame window was quit
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit();
            sys.exit();

def update(algorithm, swap1=None, swap2=None, display=display): # The function responsible for drawing the sorted array on each iteration
    display.fill(pygame.Color("#a48be0"))
    pygame.display.set_caption("Sorting Visualizer     Algorithm: {}     Time: {:.3f}      Status: Sorting...".format(algorithm.name, time.time() - algorithm.start_time)) # Display on title bar
    k = int(dimensions[0]/len(algorithm.array))
    for i in range(len(algorithm.array)):
        colour = (80, 0, 255)
        if swap1 == algorithm.array[i]:
            colour = (0,255,0)
        elif swap2 == algorithm.array[i]:
            colour = (255,0,0)
        # The most important step that renders the rectangles to the screen that gets sorted.
        # pygame.draw.rect(dsiplay_window, color_of_rectangle, size_of_rectangle)
        pygame.draw.rect(display, colour, (i*k,dimensions[1],k,-algorithm.array[i]))
    check_events()
    pygame.display.update()

def keep_open(algorithm, display, time): # Keep the window open until sort completion
    pygame.display.set_caption("Sorting Visualizer     Algorithm: {}     Time: {:.3f}      Status: Done!".format(algorithm.name, time))
    while True:
        check_events()
        pygame.display.update()

def main():
    if len(sys.argv) < 2:
        print("Please select a sorting algorithm.") 
    else:
        try:
            algorithm = algorithms[sys.argv[1]] # Pass the algorithm selected
            try:
                time_elapsed = algorithm.run()[1]
                keep_open(algorithm, display, time_elapsed)
                pass
            except:
                pass
        except:
            print("Error.")

if __name__ == "__main__":
    main()

是的!我知道，有很多代碼需要消化，但我向您保證，當(dāng)您按下運(yùn)行按鈕時(shí)，所有代碼都將變得有趣。

讓我來解釋一下可視化器的代碼。

結(jié)果

是時(shí)候運(yùn)行我們的項(xiàng)目了。在項(xiàng)目目錄中打開終端并執(zhí)行 python visualizer.py list 獲得所有可用算法的列表。

Available algorithms:
        SelectionSort
        BubbleSort
        InsertionSort
        MergeSort
        QuickSort

比如執(zhí)行：python visualizer.py SelectionSort

PS：在運(yùn)行過程中發(fā)現(xiàn)有一處代碼不對(duì)，修改如下：

def update(algorithm, swap1=None, swap2=None, display=display):
    # The function responsible for drawing the sorted array on each iteration
    display.fill(pg.Color("#a48be0"))

    pg.display.set_caption("Sorting Visualizer 11    Algorithm: {}     Time: {:.3f}      Status: Sorting...".format(algorithm.name, time.time() - algorithm.start_time)) # Display on title bar
    k = int(dimensions[0]/len(algorithm.array))
    for i in range(len(algorithm.array)):
        colour = (80, 0, 255)
        if swap1 == algorithm.array[i]:
            colour = (0,255,0)
        elif swap2 == algorithm.array[i]:
            colour = (255,0,0)
        # 設(shè)置幀率為每秒60幀
        # The most important step that renders the rectangles to the screen that gets sorted.
        # pg.draw.rect(dsiplay_window, color_of_rectangle, size_of_rectangle)
        pg.draw.rect(display, colour, (i*k, 512 - algorithm.array[i], k, algorithm.array[i]))
    time.sleep(0.3)
    check_events()
    pg.display.update()

以上就是使用Python可視化展示排序算法的詳細(xì)內(nèi)容，更多關(guān)于Python可視化展示算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: