【Scratch】選擇排序法

選擇排序法是一個非常好理解的排序演算法，雖然它的效能並不好，但是對於初學者來說卻很好理解，因此是初學演算法的同學一個非常好的入門練習。先來看看在Youtube上別人拍好的說明影片：

雖然在範例中是以C++語言來實作，但是別擔心，只要同學們瞭解原理，也可以輕易地利用任何你熟悉的程式語言實作出來，當然這也包括Scratch這一類的積木式語言。

假設要排序一串數字，當然同學們一定要有一個清單用來儲存這些數字，之後就可以利用索引取出其中的單一項目做運算。假設我們在這裡建立了一個叫做numbers的清單：

接著要為這個清單加一些數字上去，所以在開始執行程式的時候，就建立一個想要用來排序的清單項目：

執行結果如下：

從演算法的說明中可以看到，在執行的過程中我們需要有2個變數做為索引值，一個是要指向目前是要找的是第幾個數字（x），而另外一個則是要指出目前正要比較的那個索引位置（y），此外還要有一個變數用來暫存目前最小值（smallest）、最小值的那個數的索引位置（smallestIndex）以及要用來做交換的暫存變數（temp），分別定義如下：

當角色被點擊的時候，先把第一個要被比較的對象x設定為1，並設定總共要比較的次數，假設有n個數，就要比較n-1次，因此迴圈的設定如下：

由上述的程式積木便可看出，n其實就是清單的項目數。接著要開始進行每一遍的比較之前，需要設定一些變數如下：

如上所述，先把x當做是目前最小值所在的位置，而目前的最小值當然就是x這個位置的內容。要開始比較的那些項目，就從y開始，而y其實就是要從x的右邊那個開始，也就是x+1。接著，就要把右邊的數字一個一個取出來比較，所以需要一個迴圈如下：

在這個迴圈中，我們就把y索引所指到的位置之內容拿來看目前的最小值進行比較，如果有小於的情形，就要更新目前最小值的索引以及對像，上述的迴圈內，需要加上的程式積木如下：

上面這個迴圈每執行完一遍，就可以得到被比較對象們的目前最小值和其索引，分別放在smallest以及smallIndex中，因此我們就要在進行下一輪的比較之前，先看看是否smallIndex不同於x，如果是的話，就要對2個位置的內容進行交換，最後再把x加1，進入下一輪的比較，這一段的程式積木如下：

完整的程式積木如下所示：

以下是程式的運行結果：

 

 

(3639)