## week13_1130_演算法_排序

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

8.1 認識演算法<br>

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

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

### [inclass practice]

### {範例}

1. 由小排到大排序

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]

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]

### [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)

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)

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)

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>