冒泡排序算法演示装置的设计与实现

王浩璇　陆思良　刘永斌　舒玉恒

摘 要 冒泡排序算法演示装置由展台模块、机械臂模块、移动平台模块和电脑组成。以物体体积大小代表数字大小，根据冒泡排序算法，使用机械臂对待排序物体进行排序，并将初始顺序、排序过程及排序结果显示在电脑屏幕上。该装置具有结构简单、操作便捷、互动性强等特点，能帮助观众直观地理解冒泡排序算法的执行过程。

关键词 冒泡排序算法 演示装置 教学仪器

0 引言

随着科技的不断发展，科普展览的智能化水平也在不断提高。近年来，智能机器人技术逐渐成为展示的热点，其在展示智能化技术的同时，还能与观众进行交互，让观众亲身体验新技术给日常生活带来的改变。

排序是指一串记录按照其中的某个或某些关键字的大小，以递增或递减的形式排列。该操作在自动控制、网页搜索、数字办公中大量使用。排序算法就是如何使得数据按照要求排列的方法。冒泡排序法是排序算法中的一种，它的算法思想是：从数组中的第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数中的最大数并“冒泡”至数列的顶端。

算法是当今智能领域的技术核心，但算法的学习过程非常枯燥，对于初学者而言难度很大。本文所介绍的冒泡排序算法演示装置，利用机械臂组成机械装置，完成待排序物块的调换，并借助传感器进行光电检测，通过电脑端进行图像处理，最终实现对冒泡排序算法的直观演示。

1 冒泡排序算法的原理

1.1 基本思想

数组R的数据总数为n，将R1……Rn垂直排列，其中Ri为数组的第i个元素。将数组中的数据视为重量不同的气泡，根据“轻者在上，重者在下”的原则，从下往上互相比较，凡是违反原则的轻气泡，就使其向上“漂浮”，如此反复进行。

1.2 排序过程

如图1所示，比较数组的第一个数R1与第二个数R2，若为逆序，即R1>R2，则交换；比较数组的第二个数R2与第三个数R3，若为逆序则继续交换；依次类推，直至Rn-1与Rn完成比较为止。第一次冒泡排序结束后，最大的数被放置在最后一位。对前n-1个数进行第二次冒泡排序，使第二大的数被安置在此时的最后一位。重复上述过程，共经过n-1次冒泡排序后，整个排序流程结束。

2 演示装置的硬件组成

如图2所示，冒泡排序算法演示装置包括展台模块、机械臂模块、移动平台模块和电脑。

2.1 展台模块

如图3所示，展台模块由摄像头、待排序物块和支架组成。待排序物块均匀地排列在支架上，以其体积大小作为排序依据。摄像头位于待排序物块的正上方，对待排序物块进行拍摄，采集待排序物块的体积大小。经过电脑图像处理，将待排序物块的顺序信息输送给控制器。

2.2 机械臂模块

如图4所示，机械臂模块由舵机、丝杠电机、升降平台、控制器、光轴、T型手臂和机械爪组成。机械爪与T型手臂相连，其中心间距与相邻两个待排序物块的中心间距相同，通过电机把动力传给丝杠，丝杠带动螺母进行位移。机械爪具有多个自由度，使其运动自如，提高了作业的效率。T型手臂与升降平台上的舵机相连，可在竖直方向上进行旋转，实现待排序物块的位置调换。升降平台的升降由丝杠电机实现，丝杠电机与两根光轴在平台上成三角形放置。控制器则与电脑、舵机、丝杠电机、驱动电机、红外循迹传感器相连。

2.3 移动平台模块

如图5所示，移动平台模块由轨道、标记、机器人底座、轮子、红外循迹传感器、驱动电机和V槽轮组成。其中，标记位于两根轨道的中间，相邻两个标记的间距为相邻两个待排序物块的中心间距。驱动电机位于机器人底座上，用于水平方向的移动。红外循迹传感器则位于机器人底座的前端，用于检测标记及定位。

3 演示装置的软件程序

3.1 图像处理方法

（1）图像灰度化处理

摄像头采集的图像一般为RGB色彩模式，必须进行图像灰度化处理，以减小原始数据量，便于后续处理。灰度是指色彩的浓淡程度，约为0～255（0为黑色，255为白色）。彩色图像进行图像灰度化处理后，虽然减少了图像信息，丢失了一些颜色等级，但是从整体来看，灰度图像的描述与彩色图像基本一致，并且极大加快了之后的运算速度。

（2）圖像二值化处理

图像二值化处理是指通过选取适当的阈值，使得图像上的点非黑即白。当图像的灰度值大于或等于阈值时，该像素的灰度值用255表示，即为白色；当图像的灰度值小于阈值时，该像素的灰度值用0表示，即为黑色。图像的二值化减小了图像的数据量，有利于进一步分析处理，而且使得图像的轮廓更加清晰。

（3）图像增强处理

图像增强处理是指采用一系列技术去改善图像的视觉效果。根据不同的应用场合，我们对图像进行针对性处理，突出那些需要的图像特征，同时抑制不感兴趣的图像特征。

3.2 光电检测原理

光电检测具有电路设计简单、检测信息速度快和成本相对低廉的优点。冒泡排序算法演示装置根据光电检测的原理，利用红外循迹传感器进行检测标记及定位。红外循迹传感器根据红外线在不同颜色的物体表面反射强度的不同，在机器人底座的行驶过程中向地面不断发射红外线，当经过白色区域时红外线发生反射，反射光被装在底座上的接收管接收；当经过黑色区域时红外线被吸收，底座上的接收管接收不到红外线。

4 演示装置的算法实现

当演示开始时，摄像头先采集待排序物块的图像，再经过电脑处理，将待排序物块的顺序信息输送给控制器，控制器控制装置移动以及调换待排序物块。当装置移动到第一个标记处时，若两个待排序物块需要调换位置，则升降平台下降至与待排序物块同一高度处，机械爪抓取物块，升降平台上升，T型手臂旋转，使待排序物块位置调换，随后升降平台下降，机械爪放下待排序物块。接着，升降平台重新上升，装置前移至下一标记：如需调换，重复上一步骤；如不需调换，则直接移至下处。当装置移到最后一个比较点时，第一轮排序结束，装置回到初始位置开始下一轮排序。待所有排序完成后，装置自动复位。电脑端图形用户界面可实时显示初始状态及排序过程，用户只需在电脑上操作即可实现重复排序。

5 结语

冒泡排序算法是计算机数据处理中常用的一种比较算法。冒泡排序算法演示装置利用物体体积大小代表数字大小，将计算机程序软件执行的数字大小排序转化为物体大小的移动排序，让观众深刻地理解冒泡排序算法的科学原理。

本装置寓教于乐、融教于趣，观众可自行打乱物体的排序，再通过操作还原，实现了有效的人机互动。此外，本装置为模块化结构，设计简洁、方便拆装，并能根据实际情况设计尺寸大小，既可制成大型装置用于场馆科普展示，也可做成小型装置用于课堂教学演示。

参考文献

[1]陆思良，周天昊，苏杰，等.一种冒泡排序算法演示装置：201710723948.3[P].2017-11-24.

[2]罗国明.冒泡排序动态演示算法设计[J].福建电脑，2013（1）：19-20.

[3]谢作如.结合生活经验，注重算法的实际应用——《冒泡排序》教学设计点评[J].中国信息技术教育，2011（11）：29-30.

[4]邱秀荣，赵莉苹，蔡镔.基于Flash的冒泡排序算法的演示实现[J].安阳工学院学报，2011（6）：48-49，63.

[5]章婷红.《冒泡排序算法》教学设计[J].中小学信息技术教育，2008（4）：27-30.