冒泡排序算法演示裝置的設(shè)計與實現(xiàn)

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

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

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

0 引言

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

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

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

1 冒泡排序算法的原理

1.1 基本思想

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

1.2 排序過程

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

2 演示裝置的硬件組成

如圖2所示，冒泡排序算法演示裝置包括展臺模塊、機械臂模塊、移動平臺模塊和電腦。

2.1 展臺模塊

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

2.2 機械臂模塊

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

2.3 移動平臺模塊

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

3 演示裝置的軟件程序

3.1 圖像處理方法

（1）圖像灰度化處理

攝像頭采集的圖像一般為RGB色彩模式，必須進行圖像灰度化處理，以減小原始數(shù)據(jù)量，便于后續(xù)處理?；叶仁侵干实臐獾潭龋s為0～255（0為黑色，255為白色）。彩色圖像進行圖像灰度化處理后，雖然減少了圖像信息，丟失了一些顏色等級，但是從整體來看，灰度圖像的描述與彩色圖像基本一致，并且極大加快了之后的運算速度。

（2）圖像二值化處理

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

（3）圖像增強處理

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

3.2 光電檢測原理

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

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

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

5 結(jié)語

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

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

參考文獻(xiàn)

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

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

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

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

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