知名搜尋與排序演算法

過去的電腦科學家，根據演算法設計策略，發展出各種排序、搜尋資料的演算法，讓我們在這個章節做介紹，並且使用Python來進行實際操作。

排序演算法

• 採取列舉法策略
  • Bubble Sort
  • Quick Sort
  • Insertion Sort
• 採取分治法策略
  • Selection Sort
  • Merge Sort (補充教材)
  • Heap Sort (補充教材)

氣泡排序法(Bubble Sort)

藉由逐次比較相鄰的兩筆資料，並依照排序條件(由大至小或由小至大)交換資料直到排序完成為止

from random import randint

# 宣告亂數產出一組n個數字範圍在min~max的List
def random_sample_list(num, min, max):
  sample_list = []
  count = 0
  while count < num:
    tempRandNum = randint(min,max)
    if not(tempRandNum in sample_list):
      sample_list.append(tempRandNum)
      count += 1
  return sample_list

def bubble_sort(sample_list):
  for i in range(0, len(sample_list), 1):
    for j in range(0, len(sample_list)-i-1, 1):
      if sample_list[j] > sample_list[j+1]:
        tmp = sample_list[j]
        sample_list[j] = sample_list[j+1]
        sample_list[j+1] = tmp
  return sample_list

sample_list1 = random_sample_list(6, 0, 100)
print(sample_list1)
print(bubble_sort(sample_list1))

插入排序法(Insertion Sort)

插入排序法的原理是，從未排序的數列裡，每次取一個值並逐一和已排序的數列進行比較，並插入到已排序的數列中

from random import randint

# 宣告亂數產出一組n個數字範圍在min~max的List
def random_sample_list(num, min, max):
  sample_list = []
  count = 0
  while count < num:
    tempRandNum = randint(min,max)
    if not(tempRandNum in sample_list):
      sample_list.append(tempRandNum)
      count += 1
  return sample_list

# 宣告插入排序法的Function
def insertSort(sourceList):
  # 從第一個值開始取
  for i in range(0, len(sourceList), 1):
    # 先將要比較的值暫存起來(以下稱它暫存值)
    tempNum = sourceList[i]

    # 將暫存值逐一和前面的值做比較，如果小於前面的值則將前面的值往後放
    for j in range(i-1, -1, -1):
      if tempNum < sourceList[j]:
        # 比較完後，將所有值往後放，暫存值插入到適合的位置
        sourceList[j+1] = sourceList[j]
        sourceList[j] = tempNum
    print(f"Round {i}: {sourceList} ")
  
  return sourceList

# 印出原始List
sampleList = random_sample_list(6, 0, 100)
print(sampleList)

# 列印排序後結果
print(insertSort(sampleList))

選擇排序法(Selection Sort)

選擇排序法(Selection Sort)是從未排序的數列中選取最小（或最大）的元素，放置到排序數列的起始位置，直到所有數列皆排序完畢。

1. 給定一個數字組合和初始最小值位值（一開始 index 為 0）
2. 經過第一輪每個數字和最小值比較，將取出的最小值和第一個數字位置對調（選擇最小的值）
3. 接著除了第一個已排序好的數字外，其餘數字持續最小值比較（index 為 1），若有更小值則和 index 為 1（第二個）值互換
4. 持續進行比較到能比較的值只剩下一個，則由小到大的排序完成

1. 時間複雜度皆為 O(n^2)
2. 所需儲存空間不因輸入個數改變。僅儲存一個 index 值，故空間複雜度為 O(1)

from random import randint

# 宣告亂數產出一組n個數字範圍在min~max的List
def random_sample_list(num, min, max):
  sample_list = []
  count = 0
  while count < num:
    tempRandNum = randint(min,max)
    if not(tempRandNum in sample_list):
      sample_list.append(tempRandNum)
      count += 1
  return sample_list

def selection_sort(num_list):
    for i in range(0, len(num_list),1):
      min_index = i
      for j in range(i + 1, len(num_list), 1):
        if num_list[min_index] > num_list[j]:
          min_index = j
        # 交換
        tmp = num_list[min_index]
        num_list[min_index] = num_list[i]
        num_list[i] = tmp
      print(f"Round {i}: {num_list} ") 
    return num_list

sample_list = random_sample_list(6, 0, 100)
print(sample_list)
selection_sort(sample_list)

快速排序法(Quick Sort)

快速排序法是排序演算法的一種，使用Divide and Conquer的演算法來實作。其概念是從數列中挑選一個基準點，大於基準的放一邊，小於的放一邊，如此循環最後可完成排序。

以上的步驟中：

pivot可以任意挑選，在此是固定挑選數列(矩陣)的最後一個元素。
在「新的數列」上只是重複相同的步驟(選pivot、調整數列)，可以利用遞迴(recursion)處理。

from random import randint

# 宣告亂數產出一組n個數字範圍在min~max的List
def random_sample_list(num, min, max):
  sample_list = []
  count = 0
  while count < num:
    tempRandNum = randint(min,max)
    if not(tempRandNum in sample_list):
      sample_list.append(tempRandNum)
      count += 1
  return sample_list

def partition(sample_list, low, high):
  i = low - 1
  for j in range(low, high, 1):
    if sample_list[j] <= sample_list[high]:
      i = i + 1
    tmp = sample_list[i+1]
    sample_list[i+1] = sample_list[high]
    sample_list[high] = tmp

    return i

def quick_sort(sample_list, low, high):
    if low < high:
      key_Index = partition(sample_list, low, high)
      quick_sort(sample_list, low, key_Index)
      quick_sort(sample_list, key_Index + 1, high)

    else:
      return sample_list

sample_list = random_sample_list(6, 0, 100)
print(sample_list)
quick_sort(sample_list, 0, len(sample_list)-1)
print(sample_list)

排序法總結

排序演算法	時間複雜度	空間複雜度
氣泡排序法	O(n)~O(n2)	O(1)
選擇排序法	O(n2)	O(1)
插入排序法	O(n)~O(n2)	O(1)
快速排序法	O(nlog n)	Ο(log n)~Ο(n)

搜尋演算法

我們介紹三種比較常見的資料搜尋方法

• 線性搜尋法(Linear Search)
• 二元搜尋法(Binary Search)
• 插分搜尋法(Interpolation Search)

線性搜尋法(Linear Search)

• 定義：從第一個資料開始取出，依序一一與「目標資料」相互比較，直到找到所要元素或所有資料均尋找完為止，此方法稱「線性搜尋」。
• 優點：
  1. 程式容易撰寫。
  2. 資料不須事先排序(Sorting)
• 缺點： 搜尋效率比較差(平均次數=(N+1)/2)，不管是否有排序，每次都必須要從頭到尾找一次

def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element    
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

二分搜尋法(Binary Search)

1. 定義：如果資料已先排序過，則可使用二分法來進行搜尋。二分法是將資料分成兩部份，再將鍵值與中間值比較，如鍵值相等則找到，小於再比前半段，大於再比後半段。如此，分段比較至找到或無資料為止。
2. 優點：搜尋效率佳(平均次數=Log2N)。
3. 缺點：
   • 資料必需事先排序。
   • 檔案資料必需使是可直接存取或隨機檔。

data = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def binary_search(data, key):
    #設置選取範圍的指標
    low = 0
    upper = len(data) - 1
    while low <= upper:
        mid = (low + upper) / 2  #取中間索引的值
        if data[mid] < key:    #若搜尋值比中間的值大，將中間索引+1，取右半
            low = mid + 1
        elif data[mid] > key:  #若搜尋值比中間的值小，將中間索引+1，取左半
            upper = mid - 1
        else:                    #若搜尋值等於中間的值，則回傳
            return mid
    return -1


index = binary_search(data, 5)
if index >= 0:
    print("找到數值於索引 " + str(index))
else:
    print("找不到數值")

插分搜尋法(Interpolation Search)

插分搜尋法是基於二元搜尋法優化的搜尋演算法，藉由目前搜尋範圍的近似線公式來導出要搜尋的元素可能會存在或是可能比較接近的索引位置。

def interpolation_search(data, key):
    low = 0
    upper = len(data) - 1
    while low <= upper:
        mid = int((upper - low) * (key - data[low]) / (data[upper] - data[low]) + low)
        if mid < low or mid > upper:
            break
        if key < data[mid]:
            upper = mid - 1
        elif key > data[mid]:
            low = mid + 1
        else:
            return mid
    return -1
    
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
search_target = int(input( f"Please enter the number you want to search in\n {data}\n> ") )
index = interpolation_search(data, search_target)

if index >= 0:
    print(f"Find in index {index}")
else:
    print("not found")

tags: 資料結構與演算法