---
title: TFG 程式問題
tags: TFG
---

# Q&A
[TOC]

## 1. c++ sort() vs. qsort() ?
問題敘述:
> 有同學問說，algorithm 裡的 **sort()** 真的不會太慢嗎?
> 畢竟 **qsort()** 聽起來就像是 **"q"uick sort** 而 **sort()** 聽起來就只是普通的排序法而已。

直接講結果:
> 答案是 ==不會！== 而且反而 **sort()** 會比 **qsort()** 快一些
> 原因是，sort() 內部並不是用隨便的排序法，而是用一種叫做 **Introsort** 的排序法
>
> 另一點是關於 **Inline function** 的使用，簡單來說就是有些時候他可以將比較函式的內容直接嵌入到 sort() 內部(編譯時)，免去了呼叫/回傳函式的時間
`C++ sort() is blazingly faster than qsort() on equivalent data due to inlining.`

實驗:
> 身為一個實事求是的資專學生，應該會想要實際跑跑看到底誰快
> 可惜的是，我在 codeblock 上測出來的結果都是相反的
> 後來直接在 zerojudge 上找到題目做測試才跑出比較理想的結果
> https://zerojudge.tw/ShowProblem?problemid=a104
> ``` c++
> #include <iostream>
> #include <algorithm>
> using namespace std;
>
> int cmp(const void* lhs, const void* rhs) {
> return *(int* )lhs - *(int* )rhs;
> }
> int cmp2(int lhs, int rhs) {
> return lhs< rhs;
> }
>
> int main() {
> int N;
> while(cin>> N) {
> int arr[N];
> for(int i=0; i<N; i++)
> cin>> arr[i];
> // qsort(arr, N, sizeof(int), cmp);
> sort(arr, arr+N, cmp2);
> for(int i=0; i<N; i++)
> cout<< arr[i]<< ' ';
> cout<< endl;
> }
> }
> ```

參考資料:
- https://www.geeksforgeeks.org/c-qsort-vs-c-sort/
> As the name suggests, qsort function uses **QuickSort** algorithm to sort the given array, **although the C standard does not require it to implement quicksort.**
>
> C++ sort function uses **introsort** which is a hybrid algorithm. Different implementations use different algorithms. The GNU Standard C++ library, for example, uses a **3-part hybrid sorting algorithm**: introsort is performed first (introsort itself being a hybrid of **quicksort** and **heap sort**) followed by an **insertion sort** on the result.
>
> C++ sort() is blazingly faster than qsort() on equivalent data due to **inlining**.

- Introsort https://zh.wikipedia.org/wiki/内省排序
- 為什麼臨時才從 quicksort 轉換到 heapsort 並不會影響太多速度?
https://aquarchitect.github.io/swift-algorithm-club/Introsort/
[ ∀n \< p ] pivot [ ∀n \> p ] (當層數過深，轉換到 heapsort)
[ heap( [∀n < p] ) ] pivot [ heap( [∀n \> p] ) ]

- Inline function
https://dotblogs.com.tw/v6610688/2013/11/27/introduction_inline_function
定義 `inline bool cmp(int a, int b) { return a>b; }`
可以想像成 sort() 內的 `if( cmp(a, b) )` 有可能直接被編譯器替換為 `if( a>b )`

如何找資料:
> 其實蠻單純的，就是直接用 google 找就是了，但有幾個小技巧
> 英文還是比較容易找到跟程式相關的資料，不過中文也慢慢找的到越來越多資料了，尤其是大陸一些論壇的討論，所以讀英文外、有些簡體字也要看的懂。
>
> 網路上有真的資料、當然也有假的資料，所以慎選資料來源，比如 geeksforgeeks, stackoverflow 就不錯，越多人回應的資料就越能相信它的真實性

關於 sort:
> 在找資料的途中也發現了一些可以分享的小知識
> sort 分為 stable 與 unstable
https://zh.wikipedia.org/wiki/排序算法#穩定性
>
> 另外，有些排序的想法蠻特別的，並不是單純的比較、交換
> 像是 [Counting sort](https://magiclen.org/counting-sort/), [Radix sort](https://magiclen.org/radix-sort/), [Bucket sort](https://magiclen.org/bucket-sort/) 等
> 練習: https://zerojudge.tw/ShowProblem?problemid=d190
> 其他參考 https://zh.wikipedia.org/wiki/比较排序#算法特例
>
> 看了這麼多排序相關的題目，最後再寫一題有趣的題目 https://zerojudge.tw/ShowProblem?problemid=d583
>
> 想完解法之後也可以去看最下方別人的提示，你的思路是不是也已經被排序綁架了呢?

[:house:](https://hackmd.io/@oscar-lin/TFG)