基于OpenGL的常用排序算法可視化系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

魏 莉

(安徽廣播電視大學(xué) 信息與工程學(xué)院 ，合肥 230022)

一、引言

排序算法(Sorting algorithm)是一種能將一串?dāng)?shù)據(jù)依照特性排序方式進(jìn)行排列的一種算法。最常用的排序方式是數(shù)值排序以及字典排序。算法可視化是將一段程序的數(shù)據(jù)、操作、語(yǔ)義進(jìn)行抽象，并對(duì)這些抽象進(jìn)行動(dòng)態(tài)的圖像展示[1]。數(shù)據(jù)結(jié)構(gòu)中的排序算法本身具有算法思想、算法流程等知識(shí)化的概念，在計(jì)算機(jī)中體現(xiàn)為算法代碼。算法可視化的一個(gè)任務(wù)就是將算法中所涉及的知識(shí)進(jìn)行具象化，將代碼可視化為對(duì)應(yīng)的算法動(dòng)畫(huà)，讓學(xué)習(xí)者能夠很快建立起算法與代碼之間的聯(lián)系，使之容易理解和掌握[2-4]。

OpenGL(Open Graphics Library)是一個(gè)功能強(qiáng)大的跨語(yǔ)言、跨平臺(tái)的專(zhuān)業(yè)底層圖形庫(kù)，除了提供基本的點(diǎn)、線(xiàn)、多邊形的繪制函數(shù)外，還提供了復(fù)雜的三維物體以及復(fù)雜曲線(xiàn)和曲面繪制函數(shù)，以及顏色模式設(shè)置、光照、紋理映射、位圖緩存等功能[5-6]。本文利用開(kāi)源圖形函數(shù)庫(kù)OpenGL工具在VC++環(huán)境下設(shè)計(jì)實(shí)現(xiàn)了三維動(dòng)態(tài)演示系統(tǒng)，提供了常用排序算法計(jì)算過(guò)程的算法可視化，便于學(xué)生理解和掌握排序算法的相關(guān)概念，并進(jìn)行編程應(yīng)用。

二、三維動(dòng)態(tài)可視化系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)

(一) 可視化系統(tǒng)概述

該可視化系統(tǒng)是在Windows操作系統(tǒng)上,以Visual Studio 2010為開(kāi)發(fā)環(huán)境，基于MFC框架的單文檔結(jié)構(gòu)和OpenGL類(lèi)庫(kù)，采用Ribbon界面進(jìn)行開(kāi)發(fā)[7]，使界面操作更加直觀，更有效率。后臺(tái)算法主要是典型的常用排序算法的計(jì)算過(guò)程，包括冒泡排序、快速排序、選擇排序、堆排序、直接插入排序、折半插入排序、希爾排序、歸并排序、基數(shù)排序、優(yōu)化的冒泡排序和快速排序共11種排序算法。三維動(dòng)態(tài)可視化系統(tǒng)演示如圖1所示。其中，A為操作控制模塊，B為算法設(shè)置模塊，C、E為三維可視化模塊，D為日歷顯示模塊。

(二) 可視化系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

從設(shè)計(jì)實(shí)現(xiàn)的角度，該可視化系統(tǒng)主要實(shí)現(xiàn)了三個(gè)方面的功能，一是人機(jī)交互的界面操作，如算法啟動(dòng)設(shè)置、速度控制、天氣模式、選擇的排序算法等初始化設(shè)置功能；二是后臺(tái)排序算法的運(yùn)算，包括常用排序算法的計(jì)算流程，以及可視化Android小人的運(yùn)動(dòng)軌跡計(jì)算等功能；三是為了更加直觀演示排序算法過(guò)程，針對(duì)三維可視化過(guò)程添加了場(chǎng)景信息，如天空、地面、Android小人等三維模型。圖2為可視化系統(tǒng)功能模塊圖。三者之間是相輔相成的，后臺(tái)算法運(yùn)算為三維可視化提供Android小人運(yùn)動(dòng)軌跡的坐標(biāo)數(shù)據(jù)，界面操作控制算法的初始化設(shè)置及運(yùn)行流程，三維可視化為后臺(tái)算法提供了顯示平臺(tái)及人機(jī)交互功能。

圖1 三維動(dòng)態(tài)可視化系統(tǒng)演示圖

圖2 可視化系統(tǒng)功能模塊圖

從可視化系統(tǒng)運(yùn)行流程過(guò)程的角度，可以將系統(tǒng)分為兩類(lèi)，一類(lèi)是創(chuàng)建工作線(xiàn)程，對(duì)算法排序過(guò)程及Android小人運(yùn)動(dòng)軌跡的坐標(biāo)進(jìn)行數(shù)據(jù)運(yùn)算及存儲(chǔ)；另一類(lèi)是創(chuàng)建界面線(xiàn)程，通過(guò)獲取當(dāng)前繪圖區(qū)域的設(shè)備描述符DC(Device Context)并設(shè)置其像素格式屬性，再創(chuàng)建渲染描述符RC(Rendering Context)，并使之與設(shè)備描述符DC綁定成為當(dāng)前繪制環(huán)境，從而利用OpenGL庫(kù)函數(shù)繪制Android小人在地面的運(yùn)動(dòng)軌跡及天空等場(chǎng)景信息。同時(shí)，為了方便學(xué)生能夠多角度觀看算法排序過(guò)程，還提供了場(chǎng)景漫游、視角切換等鼠標(biāo)、鍵盤(pán)操作，可以選擇合適的視角進(jìn)行觀察。圖3為可視化系統(tǒng)流程框圖。其中，為了幫助學(xué)生理解，該系統(tǒng)還添加了網(wǎng)絡(luò)上的排序算法的Gif動(dòng)畫(huà)演示，與本系統(tǒng)的可視化效果進(jìn)行比較及互補(bǔ)。

圖3 可視化系統(tǒng)流程框圖

三、排序算法動(dòng)態(tài)演示

(一) 三維動(dòng)畫(huà)演示

該系統(tǒng)主要以不同大小的Android小人為演示對(duì)象，用來(lái)代表排序的元素，圖4以冒泡排序算法為例，圖(a)為排序前的狀態(tài)圖；圖(b)為排序后即Android小人從左到右依次為由小到大的排序順序，從而達(dá)到冒泡排序的效果；圖(c)為排序過(guò)程中的狀態(tài)圖，其中兩個(gè)“紅色”的Android小人為需要互換且正在交換位置的兩個(gè)Android小人，通過(guò)計(jì)算出兩個(gè)正在被比較的Android小人的中心坐標(biāo)位置，讓二者均以這個(gè)中心坐標(biāo)為圓心，并以二者間的距離為直徑，順時(shí)針行走180°，即可展示出交換位置的動(dòng)態(tài)效果，以此類(lèi)推直至完成整個(gè)排序過(guò)程。

圖4 冒泡排序過(guò)程示例

圖5 不同視角演示圖

當(dāng)然，為了方便學(xué)生能夠多角度觀察算法排序的過(guò)程，系統(tǒng)可以通過(guò)鼠標(biāo)左鍵控制觀察視角的旋轉(zhuǎn)，通過(guò)鼠標(biāo)中鍵實(shí)現(xiàn)場(chǎng)景的遠(yuǎn)近縮放效果，也可以通過(guò)鍵盤(pán)方向鍵實(shí)現(xiàn)場(chǎng)景的漫游。圖5為不同視角演示圖。

(二) Gif動(dòng)畫(huà)演示

為了能有效幫助學(xué)生鞏固理論知識(shí)，提高學(xué)生的動(dòng)手能力，同時(shí)也為了與本系統(tǒng)做個(gè)對(duì)比演示及互補(bǔ)，利用MFC框架中的對(duì)話(huà)框?qū)ο髮?shí)現(xiàn)了網(wǎng)絡(luò)上的Gif動(dòng)態(tài)演示功能。圖6(a)和圖6(b)分別為冒泡排序算法的Gif動(dòng)態(tài)演示的中間過(guò)程及排序后的效果；圖6(c)和圖6(d)分別為快速排序算法的Gif動(dòng)態(tài)演示的中間過(guò)程及排序后的效果。

圖6 GIF動(dòng)態(tài)直觀演示圖

四、結(jié)語(yǔ)

本文以教學(xué)動(dòng)態(tài)演示為目的，研究了如何將抽象的排序算法進(jìn)行動(dòng)態(tài)的圖像展示，并基于MFC框架的單文檔結(jié)構(gòu)和OpenGL類(lèi)庫(kù)，采用Ribbon界面和對(duì)話(huà)框結(jié)構(gòu)實(shí)現(xiàn)了常用算法的三維動(dòng)態(tài)可視化演示系統(tǒng)，力求將復(fù)雜的排序算法過(guò)程生動(dòng)、形象地展示在學(xué)生面前。在激發(fā)學(xué)生的學(xué)習(xí)興趣基礎(chǔ)上，加深學(xué)生對(duì)排序算法計(jì)算過(guò)程的理解，同時(shí)也能降低老師的授課難度和教學(xué)工作量，為復(fù)雜算法或邏輯有關(guān)的教學(xué)提供一種高效方法。