# wk13_1130_演算法_排序與搜尋

## 【inclass practice】

{範例}
1. 由小排到大排序 \<bubble>
2. 追蹤泡沫排序法的過程 \<bubble_debuge>

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):
        if datas[j]>datas[j+1]:
            switch(j)
print(f"排序後:{datas}")

排序前:[3, 20, 10, 5]
排序後:[3, 5, 10, 20]

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)

3 5
[5, 3, 10, 20]

## 【afterclass practice】

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

### 1. 綜合演練 選擇題1-10

( C ) 1. 執行下列程式，下列結果何者正確？(A) [3,5,2,1] (B) [ 5,3,2,1] (C) [1,2,3,5] (D) [3,5,1,2 ]

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]

( D ) 2. 執行下列程式，下列顯示結果何者正確？(A) 52 (B) i (C) no (D) 3

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

3

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

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

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

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

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

( D ) 8. 執行下列程式，下列結果何者正確？(A) no = 256 (B) IsFound=True (C)共比對 9 次 (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 次

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

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

### 2. 名詞解釋 : 演算法、虛擬碼、流程圖

- 演算法:是一套有序的指令或規則，用來解決特定問題或執行特定任務的計算過程或方法。演算法可以視為一種計算的流程或步驟，它接受輸入資料，經過一系列的處理步驟，最終產生輸出結果。

- 虛擬碼:又稱為偽代碼，是一種高層次描述演算法的方法。它不是現實存在的程式語言（已經出現了類似虛擬碼的語言，參見Nuva）；它可能綜合使用多種程式語言的語法、保留字，甚至會用到自然語言。它以程式語言的書寫形式指明演算法的職能。相比於程式語言（例如Java、C++、C、Delphi 等等）它更類似自然語言。它是半形式化、不標準的語言。我們可以將整個演算法執行過程的結構用接近自然語言的形式（這裡可以使用任何一種作者熟悉的文字，例如中文、英文，重點是將程式的意思表達出來）描述出來。使用虛擬碼，可以幫助我們更好地表述演算法，不用拘泥於具體的實現。

- 流程圖:又稱程式方塊圖是表示演算法、工作流或流程的一種方塊圖表示，它以不同類型的框代表不同種類的步驟，每兩個步驟之間則以箭頭連接。這種表示方法便於說明解決已知問題的方法。流程圖在分析、設計、記錄及操控許多領域的流程或程式都有廣泛應用。