Comparison Sort

The following is base on ascend order

• In-place vs Out-place:
  問題規模是n
  In-place: 只需要常數空間(跟n無關)
  out-place: 需要n空間
• Bubble sort:

1. 比較相鄰的2個數值, 較大的往右移
2. 2層迴圈
   第1輪 -> 最大的擠到最後一個
   第2輪 -> 次大的擠到倒數第二個
   …
3. 比較過程沒有swap表示, 剩下的數已經排好

bubble sort link list

• Selection sort:

1. select min. element place it at beginning of subarr
2. subarr: sorted
   1st: place min at beginning of arr[0…len-1]
   2nd: place min at beginning of arr[1…len-1]
   …

ref:

選擇排序(Selection Sort)演算法，最簡單的排序演算法

• Insert sort:

排撲克牌, 準備插入的牌:key, 被比較的牌: cur
if cur > key
cur 往右移1格
else
key插在cur後面

延伸：

1. Binary Insertion Sort
2. implement via link list

• Quick sort:

1. Divide and conquer: 大問題分成小問題處理
2. partition:

(1)pick pivot:
a. first element
b. last element

比pivot小, 往前放

c. median element
d. random element

(2)
put all smaller elements before pivot
put all larger elements after pivot

3. worst case:
3.1 smallest/largest as pivot
3.2 array is already sorted in increasing or decreasing order

4. best case: middle as pivot

5. advance:
a. 3-way QuickSort: array divide 3 parts
b. implement for link list

6. Why QuickSort is preferred over MergeSort for sorting Arrays
6.1 MergeSort需要額外space N
…

7. Why MergeSort is preferred over QuickSort for Linked Lists?
access 問題, In linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have continuous block of memory

------------------------------------------

結語：QuickSort很常用, 改變pivot可以避開worst case

ref:

Comparison Sort: Quick Sort(快速排序法)

• Merge sort:

1. Divide and conquer
   分成 lArr, rArr, -> merge時比較lArr[i] vs rArr[j] 大小, 放到arr[k]
2. Merge Sort is useful for sorting linked lists in O(nLogn) time 還沒讀
3. Implement with linked list

a. 把link list拆成fornt_hal, back_hal, 拆到剩1個node
b. 把拆過的link list組起來

• Heap sort: based on Binary Heap data structure, similar to Selection sort which repeat the same process for the remaining elements.

1. Binary Heap:
   1.1 As Complete Binary Tree
   Index: starting index = 0
   parent((i-1)/2)
   left child(2i+1)
   right child(2i+2)

Complete Binary Tree

1.2 stored in a special order
a. Max Heap: parent > childrens
b. Min Heap: parent < childrens

2. Heapify:
2.1 reshaping the a Binary tree to Binary heap
2.2 Performed in bottom-up order: heapify procedure can be applied to a node only if its children nodes are heapified(left node一定是heapified).

3. 流程:
3.1 build Max Heap(max element在root)
3.2 把root換到最後一個 -> 忽略最後一個(size-1) -> 重新heapify … 直到剩餘size ≤ 1

4. 優點:
4.1 Efficiency — The time required to perform Heap sort increases logarithmically(對數成長)
4.2 memory:

ref:

Comparison Sort: Merge Sort(合併排序法)

• Counting sort:
  count[max-min+1] -> 紀錄出現的次數 -> 累加出現的次數 -> count累加的的次數 = output的index (以候補看, 未做)