\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2021年12月18日 星期六

[Counting Sort, Radix Sort] 計數排序, 基數排序

 Counting Sort是一種效率很高的排序方式,複雜度為$\ord{n+k}$,其中$k$是Bucket的大小,由此可知僅限於整數且數字範圍不能太大。根據觀察在很多應用中會有對物件以編號大小進行排序的行為,在這方面應該能做到很大的加速。

另外一個問題是Counting Sort雖然簡單,很多人甚至可以自己想到實作方法,但這也導致了標準的作法常常被人忽略。因此這裡就來給大家展示標準的Counting sort:

參數的解釋如下:

  • First, Last:
    和std::sort的定義一樣,需要排序的範圍,注意不一定要是random access iterator。
  • BucketFirst, BucketLast:
    Counting Sort正統的實作方式會有一個正整數陣列作為Bucket,考量到各種應用所以這裡接傳Bucket的範圍進來能做的優化會比較多,必須要是random access iterator。
  • OutputFirst:
    Counting Sort的output是直接將input存到另一個陣列中,因此OutputFirst指的是Output陣列的開頭,必須要是random access iteator,且要注意output的空間是足夠的。這邊將input存進output時是用std::move的方式,如果想要保留原本input的話可以將其拿掉。
  • Key:
    這是一個函數,Key(x)必須要回傳一個0~(BucketLast-BucketFirst-1)的正整數作為被排序物件x的關鍵值。
有了Counting sort,Radix Sort就比較好解釋了。首先正統的Counting sort是stable sort,所以Key值相同的東西排序前後的先後順序是不變的。因此可以透過多次的Counting Sort來完成一些原本Counting Sort無法完成的事情。
以整數(int, -2147483648~2147483647)排序為例,可以先針對第十億位做為Key進行排序,接著再對第一億位做為Key、第一千萬位做為Key...直到十位數、個位數作為Key,最後再以正負號最為Key進行排序,這樣就可以完成一般範圍的整數排序。
實際上一般不會這樣用,通常是用在有多個Key值的情況,以下面的程式碼來說,可以自行執行看看花費的時間有多少:

2021年12月13日 星期一

[Discretizer] 離散化器

離散化是演算法競賽常用的操作,在各種實際問題上也能看到其應用。最基本的情況,是對於n個可排序的元素,製造一個map使得它們可以和自己的名次一一對應,但通常的應用中這n個元素確定之後就不太會有增減的動作,因此可以存到vector中排序去除重複的部分,搜索的部分就用二分搜尋來取代。