### Wk14_B1121138_邱冠誠
ch08_演算法_排序與搜尋

8.1 認識演算法

8.2 排序

泡沫排序
追蹤泡沫排序過程
8.3 搜尋

循序搜尋
二分搜尋

【inclass practice】

{綜合演練}

實作2 :

俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，
讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，
並顯示其結果。

實作3:

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

def switch(i) :
    datas[i], datas[i+1] = datas[i+1], datas[i]
    
datas = [31,5,12,1]

print("排序前", datas)

n = len(datas)

#for i in range(0, n-1):
for i in range(n-1):
    #print(f"i = {i}, j= {j}", end=" ")
    for j in range(0, n-1-i):
        print(f"i = {i}, j= {j} : [j]={datas[j]}, [j+1]={datas[j+1]}", end=" ")
        if datas[j] > datas[j+1] :
            switch(j)
            print(f"交換後 : [j]={datas[j]}, [j+1]={datas[j+1]}", end="\n ")  
        else :
            print(f"不交換 \n")
    print(f"{datas} \n" )


print("排序後", datas)

排序前 [31, 5, 12, 1]
i = 0, j= 0 : [j]=31, [j+1]=5 交換後 : [j]=5, [j+1]=31
i = 0, j= 1 : [j]=31, [j+1]=12 交換後 : [j]=12, [j+1]=31
i = 0, j= 2 : [j]=31, [j+1]=1 交換後 : [j]=1, [j+1]=31
[5, 12, 1, 31]

i = 1, j= 0 : [j]=5, [j+1]=12 不交換

i = 1, j= 1 : [j]=12, [j+1]=1 交換後 : [j]=1, [j+1]=12
[5, 1, 12, 31]

i = 2, j= 0 : [j]=5, [j+1]=1 交換後 : [j]=1, [j+1]=5
[1, 5, 12, 31]

排序後 [1, 5, 12, 31]

# 3.中獎者姓名(循序搜尋) <sequential>
num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多"]
no = int(input("請輸入中獎者的編號："))
 
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)) 

請輸入中獎者的編號：111
無此中獎號碼！
共比對 8次

#4. 二分搜尋 : 中獎者姓名 <binary>
num=[256,731,943,389,142,645,829,945,371,418]
name=["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多","賈天良","吳水品"] 

n=len(num)-1 # 串列長度-1
IsFound=False
min=0
max=n
c=0 #計算比對次數 

for i in range(0,n): 
    for j in range(0,n-i):         
        if (num[j]>num[j+1]): # 由小到大排序
            num[j],num[j+1]=num[j+1],num[j]     # 兩數互換
            name[j],name[j+1]=name[j+1],name[j] # 姓名互換
 
no = int(input("請輸入中獎者的編號："))

while(min<=max):
    mid=int((min+max)/2)
    c+=1  #比對次數加 1
    if (num[mid]==no):  #號碼相符 
        IsFound=True
        break

    if (num[mid]>no):  #如果中間值大於輸入值 
       max=mid-1      #使用較小的一半區域繼續比對 
    else:             #如果中間值不大於輸入值 
       min=mid+1      #使用較大的一半區域繼續比對 
       
if (IsFound==True):
    print("中獎者的姓名為：",name[mid])
else:
    print("無此中獎號碼！")
print("共比對 ", c ," 次")    

請輸入中獎者的編號：256
中獎者的姓名為： 林小虎
共比對 2 次