<style>
.red {
color: red;
}
.yellow {
color : yellow;
}
</style>

# 計算機概論筆記目錄
* [Back to Catalog](https://hackmd.io/k8RM78yDSW2F3bAStO8K8A)
* Source

## Chapter 0 : Sorting & Searching
**Sorting**
* <span class="yellow">The process of a list of items into a particular order</span>
* There are many algorithms for sorting a list of items
* These algorithms vary in efficiency
* eg: 3 9 6 1 2 -> 1 2 3 6 9

**Selection Sort 選擇排序法**
* <span class="yellow">Select one value and put it in its final place in the sort list</span> , repeat for all other values
* Step
1. Find the small value of the list
2. Switch it with the value in the first position
3. Find the next smallest value in the list
4. Switch it with the value in the second position
5. Repeat until all value are placed
* Example
程式碼

**Insertion Sort插入排序法**
* <span class="yellow">Pick any item and insert it into its proper place</span> in a sorted sublist , repeat until all items have been insert
* Step
1. Consider the first item to be a sorted sublist
2. Insert the second item into the sorted sublist , shifting items as necessary to make room to insert the new addition
3. Insert the third item into the sorted sublist , shifting as necessary
4. repeat until all values are inserted into their proper position
* Example
程式碼

**Comparision**
* Similar in efficiency : order $n^2$ , $O(n^2)$
* The both have outer loops that scan all elements ,and inner loops that compare the value of outer loopwith almost all values in the list

**Quick Sort**
* A fast divide-and-conquer algorithm
* Average performance : $O(n log_2 n)$
* Worst-case performance : $O(n^2)$
* Divide : 把問題切小，但題型相同
* Conquer : 將問題以遞迴方式處理
程式碼