| Cursus | push_swap

project 介紹和演算法教學

大家好，我是話很多但程式碼短的 Leo ，今天來介紹一下在 42 共同圈裡會遇到的第一個演算法 project : push_swap ，並且提供一個（我覺得）寫起來蠻短的演算法

project介紹

首先，我們有 a,b 兩個堆疊（ stacks ），在堆疊 a 裡有一些不重複且在 int 範圍內的整數，我們想使用盡可能少的 operation 來把這些數字排序。

那麼總共有哪些 operation 們可以使用呢？

sa : (swap a) 將 a 最上面的兩個數字交換

sb : (swap b) 將 b 最上面的兩個數字交換

ss : sa+sb

pa : (push a) 將 b 最上面的數字移動到a的最上面

pb : (push b) 將 a 最上面的數字移動到b的最上面

ra : (rotate a) 將 a 最上面的數字移到a的最底下

rb : (rotate b) 將 b 最上面的數字移到b的最底下

rr : ra+rb

rra : (reverse rotate a) 將 a 最底下的數字移到a的最上面

rrb : (reverse rotate b) 將 b 最底下的數字移到b的最上面

rrr : rra + rrb

所以我們的程式執行起來應該要長這樣

為了方便理解，我們來 step by step 看看這些 operations 是怎麼排序數字的

看起來不難吧？只要把在 Piscine 用過的 bubble sort ， selection sort 拿出來用就能做完了？…當然沒那麼簡單

我們來看看評分標準

如果一開始就已經排序好了， operation 數量要是 0

stack_size == 3 時，必須在 3 個 operations 內完成

stack_size == 5 時，必須在 12 個 operations 內完成

接著stack_size == 100，stack_size == 500 則是照 operations 的數量給分

「聽說」兩個加起來要 6 分才會通過，所以目標就大概擺在各 3 分吧（1100、8500），這樣看起來，那些 O( N² ) 的演算法肯定爆炸，那我們再想想其他演算法。

演算法說明

建議大家將本篇與 https://github.com/LeoFu9487/push_swap_tutorial 搭配使用，能夠幫助理解這個演算法，總之我們進入正題

先想流程，我們大致可以照這樣的步驟來實做

step 1 ： parsing，把數字都放到堆疊a裡

step 2 ： 確認 a 是否本來就排序好了，如果是，直接結束程式

step 3 ： 如果 a 的 size ≤ 5，就呼叫 smal_stack_sort() ，否則呼叫 big_stack_sort()

我相信 parsing 和 small_stack_sort() 大家都會做（其實是我懶，有人希望我寫我再寫），所以我就分享一下我的 big_stack_sort() 吧。

首先，先來介紹一個排序法：基數排序法 (Radix sort)

當我們要排序一坨非負整數時，能使用這個排序法。

假設我們今天要排序

87 487 781 100 101 0 1

我們想像現在有 10 個箱子，分別標號 0～9 ，接著我們依序把每個數字依照個位數塞進對應的箱子裡，接著重新串連起來，再依十位數塞進箱子…以此類推

像是 87 的個位數為 7 ，我們就把他放進箱子 7，下一個數字是 487 ，個位數也是 7 ，我們也把他塞進箱子 7 ，接在 87 的後面（依照進箱子的順序決定同箱子裡誰擺前面）…直到所有數字都在箱子裡，會長這樣。

box 0    100    0
box 1    781    101    1    
box 2    
box 3
box 4
box 5
box 6
box 7     87    487
box 8
box 9

接著我們把所有數字照箱子順序接起來，同箱子的就照進箱子的順序來排

100 0 781 101 1 87 487

這時可以看到，所有數字都依照個位數的大小來排序了，對於個位數相同的數字們，則是由原本在數列裡的順序排序。

接著對十位數重複同樣的操作， 100 的十位數為 0 所以放到箱子 0 ， 0 的十位數為 0 所以也放到箱子 0 （接在 100 後面）…

box 0    100    0    101    1
box 1    
box 2    
box 3
box 4
box 5
box 6
box 7    
box 8    781   87    487
box 9

然後接起來

100 0 101 1 781 87 487

這時候，所有數字都由十位數字大小來排序，對於十位數字相同的數字，則是以個位數字大小來排序

最後，對百位數再做一次

box 0      0      1       87
box 1    100    101
box 2    
box 3
box 4    487
box 5
box 6
box 7    781
box 8    
box 9

接起來

0 1 87 100 101 487 781

這時候，所有數字都先依照百位數排序，然後是十位數，再來是個位數，因為沒有千位數，所以就排序完了。

總之，這就是基數排序法。依照個位數、十位數、百位數分別丟進各箱子裡再重新接起來。這個排序法好處是速度快，實做簡單，壞處是只能處理非負整數，遇到要排負數時就不能用了（延伸一下，字串有辦法用類似的方法排序嗎？）

那麼接下來，來看看怎麼把這個方法運用在 push_swap 吧！

如何將 radix sort 運用在 push_swap ？

首先，前面說了這方法是給非負整數使用的，所以我們先把 push_swap 的數字們簡化吧！

假如我要排序這一坨數字

87 -487 781 -100 101 0 1

目標是把他們變成

-487 -100 0 1 87 101 781
   0    1 2 3  4   5   6

把原本的數字跟 0 , 1 , 2 , … 一一對應

就可以發現把

87 -487 781 -100 101 0 1

變成

-487 -100 0 1 87 101 781

的 operations

跟把

4 0 6 1 5 2 3

變成

0 1 2 3 4 5 6

所用到的 operations 是一模一樣的

只要用這個想法，我們就能把拿到的任何數字簡化成 0 ~ N - 1，在這裡用 C++ 實做一下給大家看(只會 C 的同學也不要害怕，這裡只要把 vector<int> input 想成代表輸入整數陣列就好，vector<int> copy 的內容則跟 input 一模一樣)

vector<int> input;
//parse the things into input ...
//reminder : there is no duplicate in input
vector<int> copy = input;
sort(copy.begin(), copy.end());
for(int i = 0 ; i < input.size() ; ++i) 
    for(int j = 0 ; j < copy.size() ; ++j)
        if (input[i] == copy[j])
            input[i] = j;
//put input into stack a ...

做完後 input 的數字就都介在 0～N - 1 了（這不是效率最好的實做方法，但這應該比較簡單，想讓程式跑更快的同學可以查一下二分搜尋法或 hash, unordered_map )

總之，我們現在能用 radix sort 了！爽！

但是，分成 10 個箱子其實不好實作…那我們就分成兩個吧，只要把數字改寫成二進制，然後用 0， 1 兩個箱子，就可以更輕鬆完成了。

要使用二進制，我們可以直接把數字變成由 01 組成的字串，但其實有個更簡單快速的實作方法 ：位元運算子

以下為網路上找的介紹：

https://openhome.cc/Gossip/CGossip/LogicalBitwise.html

幾個這裡會用到的位元運算子：

>>   <<    &

>> ：右移運算子，他的功能顧名思義就是把原本的位元往右移，舉個例子來看

假設現在有個

int num = 36;

由二進制寫就是

0000 ... 0010 0100（32 bits in total）

如果我們今天使用右移運算子

printf("%d\n", num>>2);

這樣輸出的結果是 9 ，為什麼是 9 呢？其實就是

0000 ... 0010 0100 -> 36
右移2位
0000 ... 0000 1001 -> 9

原來是 36 在寫成二進位 100100 被往右移兩位後變成 1001 ，轉換成 10 進位就是 9 了。總之，>>運算子用於移動位元，而<<也同理。

printf("%d\n", 3<<2);

輸出的結果是 12 ，因為

0000 ... 0000 0011 -> 3
左移2位（多出來的位數會自動補0）
0000 ... 0000 1100 -> 12

這就是左移和右移運算子

最後，講一下 & ( AND ) 運算子（對更完整的位元運算有興趣的同學可以去查查 ^ | ! 等運算子，想知道更多位元運算的應用可以搜尋 binary index tree ，位元 dp 等等）

對一個位元來說，基本定義是

1 & 1 == 1
1 & 0 == 0
0 & 1 == 0
0 & 0 == 0

而對於兩個 int 來說，我們逐位元操作

printf("%d\n", 6&5);

輸出會是 4 ，因為

6   : 0000 ... 0 1 1 0
5   : 0000 ... 0 1 0 1
6&5 : 0000 ... 0 1 0 0 -> 4

左邊每一位都是 0&0 ，所以我們保留了 0

而a和b的右邊數來第三位都是 1 ， 1&1 == 1，所以對 a&b 而言，這一位就是 1 ，對於右邊數來第一和第二位，分別是 0&1==0 和 1&0 == 0 ，因此a&b在二進制就是 100 ，在十進制就是 4

現在回到我們的 push_swap ，假設我們今天要排序

4 0 6 1 5 2 3

其實就是排序

100 000 110 001 101 010 011

放在堆疊裡會長這樣

100
000
110
001
101
010
011
----------     ----------
a              b

接著，我們照著基數排序法的想法，把 a 當作箱子 1 ， b 當作箱子 0 ，然後從最右邊的位數開始一位一位往左看。

在看右邊數來第 i 位時，如果 a 頂端的數字的第 i 位數為 0 ，就使用 pb 把這個數字丟到堆疊 b，反之，如果這位數為 1 我們就 ra 把他推到 a 的最底下，這樣就能保證遍歷全部數字後，堆疊 a , b 內都保持原本的順序，只是第 i 位為 0 , 1 被分別放進兩個不同堆疊，這就是基數排序法分箱子的部份

所以在檢查完右邊數來第一位數後，兩個堆疊會變成這樣，最右邊那位是 1 的數字都留在 a ，是 0 的都丟到 b

               010
001            110
101            000
011            100
----------     ----------
a              b

然後，我們把堆疊b裡的全部數字都放回a裡面，這就是基數排序法裡把箱子接起來的部份

100
000
110
010
001            
101            
011            
----------     ----------
a              b

然後對右邊數來第二和第三位再做一樣的事

-----依照第二位數字分箱-----
               101
110            001
010            000
011            100
----------     ----------
a              b
-----------合併-----------
100
000
001
101
110            
010            
011            
----------     ----------
a              b
-----依照第三位數字分箱-----
               011
100            010
101            001
110            000
----------     ----------
a              b
-----------合併-----------
000
001
010
011
100
101
110
----------     ----------
a              b

這樣就排序完了

程式碼大概長這樣

int size = a.size();
int max_num = size - 1; // a裡最大的數字會是size - 1
int max_bits = 0; // max_num 共有幾位
while ((max_num >> max_bits) != 0) ++max_bits;
for (int i = 0 ; i < max_bits ; ++i)
{
    for(int j = 0 ; j < size ; ++j) //確保a裡的每個數字都有檢查過
    {
        int num = a.top(); // a最上面的數字
        if ((num >> i)&1) ra(); // 如果第i + 1位是1的話，留在stack a
        else pb(); //否則推到stack b
    }
    //此時分箱子完成
    while (!b.empty()) pa(); // 把兩箱子合在一起
}

程式碼中有個部份我稍微解釋一下， (num>>i)&1 的值會是 1 或 0 ，這表示num的右邊數來第 i + 1 位為 1 或 0 ，舉例來說，(5>>2)&1 == 1 因為

 5       : 101
 5>>2    :   1
(5>>2)&1 :   1

反之， (8>>2)&1 == 0

 8       : 1000
 8>>2    :   10
(8>>2)&1 :    0

此外，在這裡補上另一種寫法，讓同學可以自己想想這兩種寫法的優缺點

bool is_sorted(stack<int> & a);
// please implement this function by yourself :)
int size = a.size();
for (int i = 0 ; !is_sorted(a) ; ++i)
{
    for(int j = 0 ; j < size ; ++j)
    {
        int num = a.top();
        if ((num >> i)&1) ra();
        else pb();
     }
    while (!b.empty()) pa();
}

還有常見錯誤：

for (int j = 0 ; j < a.size() ; ++j) // ... (x)
for (int j = 0 ; j < size ; ++j)     // ... (o)

想一想，這兩個迴圈寫法有什麼差別呢？

總之，這樣就完成了！來測試看看自己的程式碼吧，各位同學可以使用我做的 tester

https://github.com/LeoFu9487/push_swap_tester

理論上應該會測出

stack_size == 100時，有至多1084個instructions (operations)

stack_size == 500 時，有至多6784個instructions (operations)

這時任務就圓滿達成了！

問題討論：

1. 用 tester 測試時每次 input 都不同，但為何 stack_size 一樣時 operations數量一樣的機率這麼高呢？
2. 這個演算法的優點是穩定，但這同時也是缺點，因為要優化到滿分有點困難，不過還是有可做的優化：我們可以看到這演算法常常在連續做幾次 pb 後又開始連續 pa ，這樣子明顯在浪費步數，要怎麼寫才能避免這樣的贅步呢？
3. 用 2 進制很方便好實做，但如果我們不用 2 進制而改用 3 進制、4進制、5進制 … n 進制來實現基數排序法，要怎麼在只有 2 個堆疊的狀況下實現？步數最低是在幾進制？還是不同 stack size 會有不同的結果？如果今天有 n 個堆疊呢？