# 【wk13_1130】演算法_排序與搜尋
<pre>
8.1 認識演算法
8.2 排序
1. 泡沫排序
2. 追蹤泡沫排序過程
8.3 搜尋
1. 循序搜尋
2. 二分搜尋
<pre/>

## 【inclass practice】

### {綜合演練}
<pre>
實作2 :
俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，
讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，
並顯示其結果。
<pre/>

<pre>
實作3:
下列名單為本期大樂透的中獎名單name=['David','Lily','Chiou','Bear','Shantel','Chynthia']，
讓使用者輸入一個姓名，輸入的字元大小寫不分，
例如輸入 david、David、DAVID都是同一人，
請以二分搜尋法檢查該名單是否中獎，
並顯示查詢結果。
<pre/>

### {範例}
1. 由小排到大排序 \<bubble>
2. 追蹤泡沫排序法的過程 \<bubble_debuge>
3. 中獎者姓名(循序搜尋) \<sequential>
4. 二分搜尋 : 中獎者姓名 \<binary>

# 1.由小排到大排序 <bubble>
def switch(i) :
    datas[i], datas[i+1] = datas[i+1], datas[i]
datas = [3, 5, 2, 89, 41, 17]

print("排序前 :", datas)

n = len(datas)

for i in range(0,n) :
    print(f"i = {i}, j = {j}", end = "")
    for j in range(0, n-1) :
        print(f"{datas[j]}, {datas[j]}", end = "")
        if datas [j] < datas [j+1] :
            switch(j)
    print(datas)

print("排序後 :", datas)

排序前 : [3, 5, 2, 89, 41, 17]

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

NameError Traceback (most recent call last)

Cell In[4], line 11
8 n = len(datas)
10 for i in range(0,n) :
---> 11 print(f"i = {i}, j = {j}", end = "")
12 for j in range(0, n-1) :
13 print(f"{datas[j]}, {datas[j]}", end = "")

NameError: name 'j' is not defined

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

print(datas)

[5, 3, 2, 1]

## 【afterclass practice】

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

( C ) 1. 執行下列程式，下列結果何者正確？

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)

(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. 執行下列程式，下列顯示結果何者正確？

num=[67,12,9,52,91,3]

no=52

for i in range(len(num)):

if (num[i]==no):

break

print(i)

(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

答案 : 2的14次方才會大於10000 !!

( A ) 7. 下列那一種搜尋方法效率最好？

(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)三者效率相同

( D ) 8. 執行下列程式，下列結果何者正確？

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

(A) no = 256 (B) IsFound=True (C)共比對 9 次 (D)以上皆非

答案 : (A) no = 100 ; (b) IsFound = False

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)以上皆非