---
# System prepended metadata

title: week13_1130_演算法_排序與搜尋
tags: [pynote]

---

## week13_1130_演算法_排序與搜尋

### ch08_演算法_排序與搜尋
 	
8.1  認識演算法<br>

8.2  排序<br>
1. 泡沫排序<br>
2. 追蹤泡沫排序過程<br>

8.3 搜尋<br>
1. 循序搜尋<br>
2. 二分搜尋<br>

### [inclass practice]

### {範例}

1. 由小排到大排序


```python
def switch(i):
    datas[i], datas[i+1] = datas[i+1], datas[i]


datas = [3,20,10,5]

print(f"排序前：{datas}")
n = len(datas)

for i in range(0, n-1):
    for j in range(0, n-1-i):
        print(f"i={i}, j={j}")
        if datas[j] > datas[j+1]:
            switch(j)
            print(f"{datas[j+1]}, {datas[j]}互換後：{datas}")
            


print(f"排序後：{datas}")
```

    排序前：[3, 20, 10, 5]
    i=0, j=0
    i=0, j=1
    20, 10互換後：[3, 10, 20, 5]
    i=0, j=2
    20, 5互換後：[3, 10, 5, 20]
    i=1, j=0
    i=1, j=1
    10, 5互換後：[3, 5, 10, 20]
    i=2, j=0
    排序後：[3, 5, 10, 20]
    


```python
print(datas[0],datas[1])

#x = datas[0]
#datas[0] = datas[1]
#datas[1] = x

datas[0], datas[1] = datas[1], datas[0]

print(datas)

```

    20 3
    [3, 20, 10, 5]
    

### 期末專題參考


```python
! pip install requests beautifulsoup4
```

    Requirement already satisfied: requests in c:\users\user\anaconda3\lib\site-packages (2.26.0)
    Requirement already satisfied: beautifulsoup4 in c:\users\user\anaconda3\lib\site-packages (4.10.0)
    Requirement already satisfied: charset-normalizer~=2.0.0 in c:\users\user\anaconda3\lib\site-packages (from requests) (2.0.4)
    Requirement already satisfied: idna<4,>=2.5 in c:\users\user\anaconda3\lib\site-packages (from requests) (3.2)
    Requirement already satisfied: certifi>=2017.4.17 in c:\users\user\anaconda3\lib\site-packages (from requests) (2021.10.8)
    Requirement already satisfied: urllib3<1.27,>=1.21.1 in c:\users\user\anaconda3\lib\site-packages (from requests) (1.26.7)
    Requirement already satisfied: soupsieve>1.2 in c:\users\user\anaconda3\lib\site-packages (from beautifulsoup4) (2.2.1)
    


```python
import requests
from bs4 import BeautifulSoup
import webbrowser

while True:
    url = requests.get("https://zh.wikipedia.org/wiki/Special:Random")
    soup = BeautifulSoup(url.content, "html.parser")
    title = soup.find(class_="firstHeading").text
    
    print(f"{title} \nDo you want to view it? (Y/N)")
    ans = input("").lower()
    
    if ans == "y":
        url = "https://zh.wikipedia.org/wiki/%s" % title
        webbrowser.open(url)
        break
    elif ans == "n":
        print("Try again!")
        continue
    else:
        print("Wrong Choice!")
        break
```

    五氟化氮 
    Do you want to view it? (Y/N)
    y
    

### [afterclass practice]
1. 綜合演練 選擇題1-10  (需抄題在markdown cell ; 有程式碼的題目要有code cell )
2. 名詞解釋 : 演算法、虛擬碼、流程圖

### {綜合演練}

1. 執行下列程式，下列結果何者正確？
datas=[3,5,2,1]  <br>
n=len(datas)-1 <br>
for i in range(0,n): <br>
	for j in range(0,n-i):   <br>      
		if (datas[j]>datas[j+1]): <br>
			datas[j],datas[j+1]=datas[j+1],datas[j] <br>
print(datas) <br>
(A) [3,5,2,1]   (B) [ 5,3,2,1]    (C) [1,2,3,5]    (D) [3,5,1,2 ]<br>
ans:(C)



```python
datas=[3,5,2,1]  
n=len(datas)-1 
for i in range(0,n): 
    for j in range(0,n-i):         
        if (datas[j]>datas[j+1]): 
            datas[j],datas[j+1]=datas[j+1],datas[j] 
print(datas)

```

    [1, 2, 3, 5]
    

2. 執行下列程式，下列顯示結果何者正確？<br>
num=[67,12,9,52,91,3]<br>
no=52<br>
for i in range(len(num)):  <br>
    if (num[i]==no): <br>
        break  <br>
print(i)<br>
(A) 52   (B) i   (C) no   (D) 3 <br>
ans:(D)


```python
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):  
    if (num[i]==no): 
        break  
print(i)

```

    3
    

3. 下列那一個排序法，在執行搜尋前必須先將資料排序？<br>
(A) 循序搜尋法 (B) 二分搜尋法  (C) 泡沫搜尋法 (D) 以上皆是 <Br>
ans:(B)

4. 有 10000 筆資料時，使用循序搜尋最少需多少次？<br>
(A) 1   (B) 10000   (C) 15   (D) 14<br>
ans:(A)

5. 有 10000 筆資料時，使用循序搜尋最多需多少次？<br>
(A) 1   (B) 10000   (C) 15   (D) 14<br>
ans:(B)

6. 有 10000 筆資料時，使用二分搜尋最多需多少次？<br>
(A) 1   (B) 10000   (C) 15   (D) 14<br>
ans:(D)

7. 下列那一種搜尋方法效率最好？<br>
(A)二分搜尋   (B)循序搜尋   (C)泡沫搜尋   (D)三者效率相同<br>
ans:(A)

8. 執行下列程式，下列結果何者正確？<br>
num=[256,731,943,389,142,645,829,945]<br>
name=["林小虎","王中森","邵木淼","李大同",<br>
				"陳子孔","鄭美麗","曾溫柔","錢來多"]<br>
no = 100 <br>
IsFound=False<br>
for i in range(len(name)):  #逐一比對搜尋 <br>
    if (num[i]==no):        #號碼相符 <br>
        IsFound=True        #設旗標為 True<br>
        break               #結束比對<br>
if (IsFound==True):<br>
    print("中獎者的姓名為：",name[i])<br>
else:<br>
    print("無此中獎號碼！")<br>
print("共比對 %d次 " %(i+1))  <br>
(A) no = 256  (B) IsFound=True   (C)共比對 9 次  (D)以上皆非<br>
ans:(D)


```python
num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同",
                "陳子孔","鄭美麗","曾溫柔","錢來多"]
no = 100 
IsFound=False
for i in range(len(name)):  #逐一比對搜尋 
    if (num[i]==no):        #號碼相符 
        IsFound=True        #設旗標為 True
        break               #結束比對
if (IsFound==True):
    print("中獎者的姓名為：",name[i])
else:
    print("無此中獎號碼！")
print("共比對 %d次 " %(i+1))

```

    無此中獎號碼！
    共比對 8次 
    

9. 同第 8 題，中獎者的姓名為？<br>
(A)錢來多   (B)曾溫柔   (C)鄭美麗   (D)無此中獎號碼！<br>
ans:(D)

10. 同第 8 題，這個程式是？<br>
(A)二分搜尋   (B)循序搜尋   (C)泡沫搜尋   (D)以上皆非<br>
ans:(B)

---

### {名詞解釋} 
演算法、虛擬碼、流程圖<br>
1. 演算法：演算法（英語：algorithm），在數學（算學）和電腦科學之中，指一個被定義好的、計算機可施行其指示的有限步驟或次序，常用於計算、數據處理和自動推理。演算法是有效方法，包含一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來。<br>
<br>
2. 虛擬碼：虛擬碼（英語：pseudocode），又稱為偽代碼，是一種高層次描述演算法的方法。它不是現實存在的程式語言（已經出現了類似虛擬碼的語言，參見Nuva）；它可能綜合使用多種程式語言的語法、保留字，甚至會用到自然語言。它以程式語言的書寫形式指明演算法的職能。相比於程式語言（例如Java、C++、C、Delphi 等等）它更類似自然語言。它是半形式化、不標準的語言。我們可以將整個演算法執行過程的結構用接近自然語言的形式（這裡可以使用任何一種作者熟悉的文字，例如中文、英文，重點是將程式的意思表達出來）描述出來。使用虛擬碼，可以幫助我們更好地表述演算法，不用拘泥於具體的實現。<br>
<br>
3. 流程圖，又稱程式方塊圖是表示演算法、工作流或流程的一種方塊圖表示，它以不同類型的框代表不同種類的步驟，每兩個步驟之間則以箭頭連接。這種表示方法便於說明解決已知問題的方法。流程圖在分析、設計、記錄及操控許多領域的流程或程式都有廣泛應用。<br>
