王浩璇　陸思良　劉永斌　舒玉恒

摘 要 冒泡排序算法演示裝置由展臺(tái)模塊、機(jī)械臂模塊、移動(dòng)平臺(tái)模塊和電腦組成。以物體體積大小代表數(shù)字大小，根據(jù)冒泡排序算法，使用機(jī)械臂對(duì)待排序物體進(jìn)行排序，并將初始順序、排序過(guò)程及排序結(jié)果顯示在電腦屏幕上。該裝置具有結(jié)構(gòu)簡(jiǎn)單、操作便捷、互動(dòng)性強(qiáng)等特點(diǎn)，能幫助觀眾直觀地理解冒泡排序算法的執(zhí)行過(guò)程。

關(guān)鍵詞 冒泡排序算法 演示裝置 教學(xué)儀器

0 引言

隨著科技的不斷發(fā)展，科普展覽的智能化水平也在不斷提高。近年來(lái)，智能機(jī)器人技術(shù)逐漸成為展示的熱點(diǎn)，其在展示智能化技術(shù)的同時(shí)，還能與觀眾進(jìn)行交互，讓觀眾親身體驗(yàn)新技術(shù)給日常生活帶來(lái)的改變。

排序是指一串記錄按照其中的某個(gè)或某些關(guān)鍵字的大小，以遞增或遞減的形式排列。該操作在自動(dòng)控制、網(wǎng)頁(yè)搜索、數(shù)字辦公中大量使用。排序算法就是如何使得數(shù)據(jù)按照要求排列的方法。冒泡排序法是排序算法中的一種，它的算法思想是：從數(shù)組中的第一個(gè)數(shù)開(kāi)始，依次遍歷數(shù)組中的每一個(gè)數(shù)，通過(guò)相鄰比較交換，每一輪循環(huán)下來(lái)找出剩余未排序數(shù)中的最大數(shù)并“冒泡”至數(shù)列的頂端。

算法是當(dāng)今智能領(lǐng)域的技術(shù)核心，但算法的學(xué)習(xí)過(guò)程非?？菰?，對(duì)于初學(xué)者而言難度很大。本文所介紹的冒泡排序算法演示裝置，利用機(jī)械臂組成機(jī)械裝置，完成待排序物塊的調(diào)換，并借助傳感器進(jìn)行光電檢測(cè)，通過(guò)電腦端進(jìn)行圖像處理，最終實(shí)現(xiàn)對(duì)冒泡排序算法的直觀演示。

1 冒泡排序算法的原理

1.1 基本思想

數(shù)組R的數(shù)據(jù)總數(shù)為n，將R1……Rn垂直排列，其中Ri為數(shù)組的第i個(gè)元素。將數(shù)組中的數(shù)據(jù)視為重量不同的氣泡，根據(jù)“輕者在上，重者在下”的原則，從下往上互相比較，凡是違反原則的輕氣泡，就使其向上“漂浮”，如此反復(fù)進(jìn)行。

1.2 排序過(guò)程

如圖1所示，比較數(shù)組的第一個(gè)數(shù)R1與第二個(gè)數(shù)R2，若為逆序，即R1>R2，則交換；比較數(shù)組的第二個(gè)數(shù)R2與第三個(gè)數(shù)R3，若為逆序則繼續(xù)交換；依次類推，直至Rn-1與Rn完成比較為止。第一次冒泡排序結(jié)束后，最大的數(shù)被放置在最后一位。對(duì)前n-1個(gè)數(shù)進(jìn)行第二次冒泡排序，使第二大的數(shù)被安置在此時(shí)的最后一位。重復(fù)上述過(guò)程，共經(jīng)過(guò)n-1次冒泡排序后，整個(gè)排序流程結(jié)束。

2 演示裝置的硬件組成

如圖2所示，冒泡排序算法演示裝置包括展臺(tái)模塊、機(jī)械臂模塊、移動(dòng)平臺(tái)模塊和電腦。

2.1 展臺(tái)模塊

如圖3所示，展臺(tái)模塊由攝像頭、待排序物塊和支架組成。待排序物塊均勻地排列在支架上，以其體積大小作為排序依據(jù)。攝像頭位于待排序物塊的正上方，對(duì)待排序物塊進(jìn)行拍攝，采集待排序物塊的體積大小。經(jīng)過(guò)電腦圖像處理，將待排序物塊的順序信息輸送給控制器。

2.2 機(jī)械臂模塊

如圖4所示，機(jī)械臂模塊由舵機(jī)、絲杠電機(jī)、升降平臺(tái)、控制器、光軸、T型手臂和機(jī)械爪組成。機(jī)械爪與T型手臂相連，其中心間距與相鄰兩個(gè)待排序物塊的中心間距相同，通過(guò)電機(jī)把動(dòng)力傳給絲杠，絲杠帶動(dòng)螺母進(jìn)行位移。機(jī)械爪具有多個(gè)自由度，使其運(yùn)動(dòng)自如，提高了作業(yè)的效率。T型手臂與升降平臺(tái)上的舵機(jī)相連，可在豎直方向上進(jìn)行旋轉(zhuǎn)，實(shí)現(xiàn)待排序物塊的位置調(diào)換。升降平臺(tái)的升降由絲杠電機(jī)實(shí)現(xiàn)，絲杠電機(jī)與兩根光軸在平臺(tái)上成三角形放置。控制器則與電腦、舵機(jī)、絲杠電機(jī)、驅(qū)動(dòng)電機(jī)、紅外循跡傳感器相連。

2.3 移動(dòng)平臺(tái)模塊

如圖5所示，移動(dòng)平臺(tái)模塊由軌道、標(biāo)記、機(jī)器人底座、輪子、紅外循跡傳感器、驅(qū)動(dòng)電機(jī)和V槽輪組成。其中，標(biāo)記位于兩根軌道的中間，相鄰兩個(gè)標(biāo)記的間距為相鄰兩個(gè)待排序物塊的中心間距。驅(qū)動(dòng)電機(jī)位于機(jī)器人底座上，用于水平方向的移動(dòng)。紅外循跡傳感器則位于機(jī)器人底座的前端，用于檢測(cè)標(biāo)記及定位。

3 演示裝置的軟件程序

3.1 圖像處理方法

（1）圖像灰度化處理

攝像頭采集的圖像一般為RGB色彩模式，必須進(jìn)行圖像灰度化處理，以減小原始數(shù)據(jù)量，便于后續(xù)處理。灰度是指色彩的濃淡程度，約為0～255（0為黑色，255為白色）。彩色圖像進(jìn)行圖像灰度化處理后，雖然減少了圖像信息，丟失了一些顏色等級(jí)，但是從整體來(lái)看，灰度圖像的描述與彩色圖像基本一致，并且極大加快了之后的運(yùn)算速度。

（2）圖像二值化處理

圖像二值化處理是指通過(guò)選取適當(dāng)?shù)拈撝?，使得圖像上的點(diǎn)非黑即白。當(dāng)圖像的灰度值大于或等于閾值時(shí)，該像素的灰度值用255表示，即為白色；當(dāng)圖像的灰度值小于閾值時(shí)，該像素的灰度值用0表示，即為黑色。圖像的二值化減小了圖像的數(shù)據(jù)量，有利于進(jìn)一步分析處理，而且使得圖像的輪廓更加清晰。

（3）圖像增強(qiáng)處理

圖像增強(qiáng)處理是指采用一系列技術(shù)去改善圖像的視覺(jué)效果。根據(jù)不同的應(yīng)用場(chǎng)合，我們對(duì)圖像進(jìn)行針對(duì)性處理，突出那些需要的圖像特征，同時(shí)抑制不感興趣的圖像特征。

3.2 光電檢測(cè)原理

光電檢測(cè)具有電路設(shè)計(jì)簡(jiǎn)單、檢測(cè)信息速度快和成本相對(duì)低廉的優(yōu)點(diǎn)。冒泡排序算法演示裝置根據(jù)光電檢測(cè)的原理，利用紅外循跡傳感器進(jìn)行檢測(cè)標(biāo)記及定位。紅外循跡傳感器根據(jù)紅外線在不同顏色的物體表面反射強(qiáng)度的不同，在機(jī)器人底座的行駛過(guò)程中向地面不斷發(fā)射紅外線，當(dāng)經(jīng)過(guò)白色區(qū)域時(shí)紅外線發(fā)生反射，反射光被裝在底座上的接收管接收；當(dāng)經(jīng)過(guò)黑色區(qū)域時(shí)紅外線被吸收，底座上的接收管接收不到紅外線。

4 演示裝置的算法實(shí)現(xiàn)

當(dāng)演示開(kāi)始時(shí)，攝像頭先采集待排序物塊的圖像，再經(jīng)過(guò)電腦處理，將待排序物塊的順序信息輸送給控制器，控制器控制裝置移動(dòng)以及調(diào)換待排序物塊。當(dāng)裝置移動(dòng)到第一個(gè)標(biāo)記處時(shí)，若兩個(gè)待排序物塊需要調(diào)換位置，則升降平臺(tái)下降至與待排序物塊同一高度處，機(jī)械爪抓取物塊，升降平臺(tái)上升，T型手臂旋轉(zhuǎn)，使待排序物塊位置調(diào)換，隨后升降平臺(tái)下降，機(jī)械爪放下待排序物塊。接著，升降平臺(tái)重新上升，裝置前移至下一標(biāo)記：如需調(diào)換，重復(fù)上一步驟；如不需調(diào)換，則直接移至下處。當(dāng)裝置移到最后一個(gè)比較點(diǎn)時(shí)，第一輪排序結(jié)束，裝置回到初始位置開(kāi)始下一輪排序。待所有排序完成后，裝置自動(dòng)復(fù)位。電腦端圖形用戶界面可實(shí)時(shí)顯示初始狀態(tài)及排序過(guò)程，用戶只需在電腦上操作即可實(shí)現(xiàn)重復(fù)排序。

5 結(jié)語(yǔ)

冒泡排序算法是計(jì)算機(jī)數(shù)據(jù)處理中常用的一種比較算法。冒泡排序算法演示裝置利用物體體積大小代表數(shù)字大小，將計(jì)算機(jī)程序軟件執(zhí)行的數(shù)字大小排序轉(zhuǎn)化為物體大小的移動(dòng)排序，讓觀眾深刻地理解冒泡排序算法的科學(xué)原理。

本裝置寓教于樂(lè)、融教于趣，觀眾可自行打亂物體的排序，再通過(guò)操作還原，實(shí)現(xiàn)了有效的人機(jī)互動(dòng)。此外，本裝置為模塊化結(jié)構(gòu)，設(shè)計(jì)簡(jiǎn)潔、方便拆裝，并能根據(jù)實(shí)際情況設(shè)計(jì)尺寸大小，既可制成大型裝置用于場(chǎng)館科普展示，也可做成小型裝置用于課堂教學(xué)演示。

參考文獻(xiàn)

[1]陸思良，周天昊，蘇杰，等.一種冒泡排序算法演示裝置：201710723948.3[P].2017-11-24.

[2]羅國(guó)明.冒泡排序動(dòng)態(tài)演示算法設(shè)計(jì)[J].福建電腦，2013（1）：19-20.

[3]謝作如.結(jié)合生活經(jīng)驗(yàn)，注重算法的實(shí)際應(yīng)用——《冒泡排序》教學(xué)設(shè)計(jì)點(diǎn)評(píng)[J].中國(guó)信息技術(shù)教育，2011（11）：29-30.

[4]邱秀榮，趙莉蘋(píng)，蔡鑌.基于Flash的冒泡排序算法的演示實(shí)現(xiàn)[J].安陽(yáng)工學(xué)院學(xué)報(bào)，2011（6）：48-49，63.

[5]章婷紅.《冒泡排序算法》教學(xué)設(shè)計(jì)[J].中小學(xué)信息技術(shù)教育，2008（4）：27-30.