基于OpenGL的常用排序算法可视化系统设计与实现

魏 莉

(安徽广播电视大学 信息与工程学院 ，合肥 230022)

一、引言

排序算法(Sorting algorithm)是一种能将一串数据依照特性排序方式进行排列的一种算法。最常用的排序方式是数值排序以及字典排序。算法可视化是将一段程序的数据、操作、语义进行抽象，并对这些抽象进行动态的图像展示[1]。数据结构中的排序算法本身具有算法思想、算法流程等知识化的概念，在计算机中体现为算法代码。算法可视化的一个任务就是将算法中所涉及的知识进行具象化，将代码可视化为对应的算法动画，让学习者能够很快建立起算法与代码之间的联系，使之容易理解和掌握[2-4]。

OpenGL(Open Graphics Library)是一个功能强大的跨语言、跨平台的专业底层图形库，除了提供基本的点、线、多边形的绘制函数外，还提供了复杂的三维物体以及复杂曲线和曲面绘制函数，以及颜色模式设置、光照、纹理映射、位图缓存等功能[5-6]。本文利用开源图形函数库OpenGL工具在VC++环境下设计实现了三维动态演示系统，提供了常用排序算法计算过程的算法可视化，便于学生理解和掌握排序算法的相关概念，并进行编程应用。

二、三维动态可视化系统的设计实现

(一) 可视化系统概述

该可视化系统是在Windows操作系统上,以Visual Studio 2010为开发环境，基于MFC框架的单文档结构和OpenGL类库，采用Ribbon界面进行开发[7]，使界面操作更加直观，更有效率。后台算法主要是典型的常用排序算法的计算过程，包括冒泡排序、快速排序、选择排序、堆排序、直接插入排序、折半插入排序、希尔排序、归并排序、基数排序、优化的冒泡排序和快速排序共11种排序算法。三维动态可视化系统演示如图1所示。其中，A为操作控制模块，B为算法设置模块，C、E为三维可视化模块，D为日历显示模块。

(二) 可视化系统设计与实现

从设计实现的角度，该可视化系统主要实现了三个方面的功能，一是人机交互的界面操作，如算法启动设置、速度控制、天气模式、选择的排序算法等初始化设置功能；二是后台排序算法的运算，包括常用排序算法的计算流程，以及可视化Android小人的运动轨迹计算等功能；三是为了更加直观演示排序算法过程，针对三维可视化过程添加了场景信息，如天空、地面、Android小人等三维模型。图2为可视化系统功能模块图。三者之间是相辅相成的，后台算法运算为三维可视化提供Android小人运动轨迹的坐标数据，界面操作控制算法的初始化设置及运行流程，三维可视化为后台算法提供了显示平台及人机交互功能。

图1 三维动态可视化系统演示图

图2 可视化系统功能模块图

从可视化系统运行流程过程的角度，可以将系统分为两类，一类是创建工作线程，对算法排序过程及Android小人运动轨迹的坐标进行数据运算及存储；另一类是创建界面线程，通过获取当前绘图区域的设备描述符DC(Device Context)并设置其像素格式属性，再创建渲染描述符RC(Rendering Context)，并使之与设备描述符DC绑定成为当前绘制环境，从而利用OpenGL库函数绘制Android小人在地面的运动轨迹及天空等场景信息。同时，为了方便学生能够多角度观看算法排序过程，还提供了场景漫游、视角切换等鼠标、键盘操作，可以选择合适的视角进行观察。图3为可视化系统流程框图。其中，为了帮助学生理解，该系统还添加了网络上的排序算法的Gif动画演示，与本系统的可视化效果进行比较及互补。

图3 可视化系统流程框图

三、排序算法动态演示

(一) 三维动画演示

该系统主要以不同大小的Android小人为演示对象，用来代表排序的元素，图4以冒泡排序算法为例，图(a)为排序前的状态图；图(b)为排序后即Android小人从左到右依次为由小到大的排序顺序，从而达到冒泡排序的效果；图(c)为排序过程中的状态图，其中两个“红色”的Android小人为需要互换且正在交换位置的两个Android小人，通过计算出两个正在被比较的Android小人的中心坐标位置，让二者均以这个中心坐标为圆心，并以二者间的距离为直径，顺时针行走180°，即可展示出交换位置的动态效果，以此类推直至完成整个排序过程。

图4 冒泡排序过程示例

图5 不同视角演示图

当然，为了方便学生能够多角度观察算法排序的过程，系统可以通过鼠标左键控制观察视角的旋转，通过鼠标中键实现场景的远近缩放效果，也可以通过键盘方向键实现场景的漫游。图5为不同视角演示图。

(二) Gif动画演示

为了能有效帮助学生巩固理论知识，提高学生的动手能力，同时也为了与本系统做个对比演示及互补，利用MFC框架中的对话框对象实现了网络上的Gif动态演示功能。图6(a)和图6(b)分别为冒泡排序算法的Gif动态演示的中间过程及排序后的效果；图6(c)和图6(d)分别为快速排序算法的Gif动态演示的中间过程及排序后的效果。

图6 GIF动态直观演示图

四、结语

本文以教学动态演示为目的，研究了如何将抽象的排序算法进行动态的图像展示，并基于MFC框架的单文档结构和OpenGL类库，采用Ribbon界面和对话框结构实现了常用算法的三维动态可视化演示系统，力求将复杂的排序算法过程生动、形象地展示在学生面前。在激发学生的学习兴趣基础上，加深学生对排序算法计算过程的理解，同时也能降低老师的授课难度和教学工作量，为复杂算法或逻辑有关的教学提供一种高效方法。