Published
- 8 min read
Searching && Sorting
Binary Search
โค้ด Binary Search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
count = 0 # นับจำนวนครั้งในการค้นหา
while left <= right:
count += 1
mid = (left + right) // 2
print(f"รอบที่ {count}: left = {left}, right = {right}, mid = {mid}, arr[mid] = {arr[mid]}")
if arr[mid] == target:
return mid, count # คืนค่าตำแหน่งและจำนวนครั้ง
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1, count # ไม่พบข้อมูล
# ข้อมูลที่ใช้ทดสอบ
data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(len(data)):
print(binary_search(data,i))
# # print('\n')ข้อมูลที่ใช้ทดสอบ:
data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]ผลลัพธ์:
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 0, right = 3, mid = 1, arr[mid] = 1
รอบที่ 3: left = 0, right = 0, mid = 0, arr[mid] = 0
(0, 3)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 0, right = 3, mid = 1, arr[mid] = 1
(1, 2)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 0, right = 3, mid = 1, arr[mid] = 1
รอบที่ 3: left = 2, right = 3, mid = 2, arr[mid] = 2
(2, 3)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 0, right = 3, mid = 1, arr[mid] = 1
รอบที่ 3: left = 2, right = 3, mid = 2, arr[mid] = 2
รอบที่ 4: left = 3, right = 3, mid = 3, arr[mid] = 3
(3, 4)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
(4, 1)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 5, right = 9, mid = 7, arr[mid] = 7
รอบที่ 3: left = 5, right = 6, mid = 5, arr[mid] = 5
(5, 3)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 5, right = 9, mid = 7, arr[mid] = 7
รอบที่ 3: left = 5, right = 6, mid = 5, arr[mid] = 5
รอบที่ 4: left = 6, right = 6, mid = 6, arr[mid] = 6
(6, 4)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 5, right = 9, mid = 7, arr[mid] = 7
(7, 2)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 5, right = 9, mid = 7, arr[mid] = 7
รอบที่ 3: left = 8, right = 9, mid = 8, arr[mid] = 8
(8, 3)
รอบที่ 1: left = 0, right = 9, mid = 4, arr[mid] = 4
รอบที่ 2: left = 5, right = 9, mid = 7, arr[mid] = 7
รอบที่ 3: left = 8, right = 9, mid = 8, arr[mid] = 8
รอบที่ 4: left = 9, right = 9, mid = 9, arr[mid] = 9
(9, 4)หลักการทำงาน
Binary Search ใช้หลักการ Divide and Conquer โดยแบ่ง List ออกเป็นสองส่วนในแต่ละรอบ และตรวจสอบว่าข้อมูลที่ต้องการค้นหาอยู่ในส่วนไหน
เงื่อนไข: List ต้องเรียงลำดับแล้ว (จากน้อยไปมากหรือมากไปน้อย)
กรณีที่ค้นหาได้เร็วสุด: ข้อมูลที่อยู่ตรงกลาง List จะถูกค้นหาได้เร็วสุด เพราะ Binary Search จะเริ่มตรวจสอบที่ตำแหน่งกลาง (mid) ก่อน
ตัวอย่าง: ใน List [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ข้อมูลที่อยู่ตรงกลางคือ 5
ขั้นตอนการทำงาน:
รอบที่ 1: left = 0, right = 9 mid = (0 + 9) // 2 = 4
ข้อมูลที่ตำแหน่ง 4 คือ 4 (ไม่เท่ากับ 5) เนื่องจาก 4 < 5 เลื่อน left เป็น mid + 1 = 5
รอบที่ 2: left = 5, right = 9 mid = (5 + 9) // 2 = 7
ข้อมูลที่ตำแหน่ง 7 คือ 7 (ไม่เท่ากับ 5) เนื่องจาก 7 > 5 เลื่อน right เป็น mid - 1 = 6
รอบที่ 3: left = 5, right = 6 mid = (5 + 6) // 2 = 5
ข้อมูลที่ตำแหน่ง 5 คือ 5 (พบข้อมูล)
สรุป: ตำแหน่งของ 5: 5 จำนวนครั้งในการค้นหา: 3
ทำไมถึงเป็นเช่นนี้?
ค้นหาได้เร็วสุด: ข้อมูลที่อยู่ตรงกลาง List จะถูกตรวจสอบในรอบแรก ทำให้ใช้เวลาน้อยที่สุด
ค้นหาได้ช้าสุด: ข้อมูลที่อยู่ตำแหน่งแรกหรือสุดท้ายของ List ต้องใช้เวลามากที่สุด เพราะ Binary Search ต้องแบ่ง List หลายรอบกว่าจะไปถึงตำแหน่งนั้น
Sorting Algorithms
ข้อมูลที่ใช้ทดสอบ:
data = [8, 7, 2, 1, 4, 9, 3, 5, 0, 6]Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # สลับค่า
print(f"รอบที่ {i + 1}: {arr}")
return arr
print("ก่อนเรียงลำดับ:", data)
sorted_data = bubble_sort(data.copy())
print("หลังเรียงลำดับ:", sorted_data)ผลลัพธ์:
ก่อนเรียงลำดับ: [8, 7, 2, 1, 4, 9, 3, 5, 0, 6]
รอบที่ 1: [7, 2, 1, 4, 8, 3, 5, 0, 6, 9]
รอบที่ 2: [2, 1, 4, 7, 3, 5, 0, 6, 8, 9]
รอบที่ 3: [1, 2, 4, 3, 5, 0, 6, 7, 8, 9]
รอบที่ 4: [1, 2, 3, 4, 0, 5, 6, 7, 8, 9]
รอบที่ 5: [1, 2, 3, 0, 4, 5, 6, 7, 8, 9]
รอบที่ 6: [1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
รอบที่ 7: [1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
รอบที่ 8: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
รอบที่ 9: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
รอบที่ 10: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
หลังเรียงลำดับ: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]หลักการทำงาน:
Bubble Sort ใช้หลักการเปรียบเทียบและสลับค่าข้อมูลที่อยู่ติดกันไปเรื่อยๆ จนกว่าข้อมูลทั้งหมดจะเรียงลำดับ
ในแต่ละรอบจะดันค่าที่มากที่สุดไปอยู่ตำแหน่งสุดท้ายของ List ที่ยังไม่ได้เรียงลำดับ
ขั้นตอนการทำงาน: รอบที่ 1:
เปรียบเทียบและสลับค่าไปเรื่อยๆ จนกว่าค่าที่มากที่สุด (9) จะไปอยู่ตำแหน่งสุดท้าย
ผลลัพธ์: [7, 2, 1, 4, 8, 3, 5, 0, 6, 9]
รอบที่ 2:
เปรียบเทียบและสลับค่าไปเรื่อยๆ จนกว่าค่าที่มากที่สุด (8) จะไปอยู่ตำแหน่งรองสุดท้าย
ผลลัพธ์: [2, 1, 4, 7, 3, 5, 0, 6, 8, 9]
ทำซ้ำจนครบทุกรอบ:
ในแต่ละรอบจะดันค่าที่มากที่สุดไปอยู่ตำแหน่งสุดท้ายของ List ที่ยังไม่ได้เรียงลำดับ
ผลลัพธ์สุดท้าย: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Selection Sort
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # สลับค่า
print(f"รอบที่ {i + 1}: {arr}")
return arr
print("ก่อนเรียงลำดับ:", data)
sorted_data = selection_sort(data.copy())
print("หลังเรียงลำดับ:", sorted_data)ผลลัพธ์:
ก่อนเรียงลำดับ: [8, 7, 2, 1, 4, 9, 3, 5, 0, 6]
รอบที่ 1: [0, 7, 2, 1, 4, 9, 3, 5, 8, 6]
รอบที่ 2: [0, 1, 2, 7, 4, 9, 3, 5, 8, 6]
รอบที่ 3: [0, 1, 2, 7, 4, 9, 3, 5, 8, 6]
รอบที่ 4: [0, 1, 2, 3, 4, 9, 7, 5, 8, 6]
รอบที่ 5: [0, 1, 2, 3, 4, 9, 7, 5, 8, 6]
รอบที่ 6: [0, 1, 2, 3, 4, 5, 7, 9, 8, 6]
รอบที่ 7: [0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
รอบที่ 8: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
รอบที่ 9: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
รอบที่ 10: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
หลังเรียงลำดับ: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]หลักการทำงาน:
Selection Sort ใช้หลักการหาค่าน้อยสุดใน List ที่เหลืออยู่และสลับกับตำแหน่งปัจจุบัน
ในแต่ละรอบจะหาค่าน้อยสุดและนำมาไว้ตำแหน่งแรกของ List ที่ยังไม่ได้เรียงลำดับ
ขั้นตอนการทำงาน: รอบที่ 1:
หาค่าน้อยสุด (0) และสลับกับตำแหน่งแรก
ผลลัพธ์: [0, 7, 2, 1, 4, 9, 3, 5, 8, 6]
รอบที่ 2:
หาค่าน้อยสุด (1) ใน List ที่เหลือและสลับกับตำแหน่งที่สอง
ผลลัพธ์: [0, 1, 2, 7, 4, 9, 3, 5, 8, 6]
ทำซ้ำจนครบทุกรอบ:
ในแต่ละรอบจะหาค่าน้อยสุดและนำมาไว้ตำแหน่งแรกของ List ที่ยังไม่ได้เรียงลำดับ
ผลลัพธ์สุดท้าย: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Insertion Sort
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
print(f"รอบที่ {i}: {arr}")
return arr
print("ก่อนเรียงลำดับ:", data)
sorted_data = insertion_sort(data.copy())
print("หลังเรียงลำดับ:", sorted_data)ผลลัพธ์:
ก่อนเรียงลำดับ: [8, 7, 2, 1, 4, 9, 3, 5, 0, 6]
รอบที่ 1: [7, 8, 2, 1, 4, 9, 3, 5, 0, 6]
รอบที่ 2: [2, 7, 8, 1, 4, 9, 3, 5, 0, 6]
รอบที่ 3: [1, 2, 7, 8, 4, 9, 3, 5, 0, 6]
รอบที่ 4: [1, 2, 4, 7, 8, 9, 3, 5, 0, 6]
รอบที่ 5: [1, 2, 4, 7, 8, 9, 3, 5, 0, 6]
รอบที่ 6: [1, 2, 3, 4, 7, 8, 9, 5, 0, 6]
รอบที่ 7: [1, 2, 3, 4, 5, 7, 8, 9, 0, 6]
รอบที่ 8: [0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
รอบที่ 9: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
หลังเรียงลำดับ: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]หลักการทำงาน:
Insertion Sort ใช้หลักการนำข้อมูลแต่ละตัวไปแทรกในตำแหน่งที่เหมาะสมใน List ที่เรียงแล้ว
ในแต่ละรอบจะนำข้อมูลมาแทรกในตำแหน่งที่ถูกต้องของ List ที่เรียงแล้ว
ขั้นตอนการทำงาน: รอบที่ 1:
นำ 7 มาแทรกในตำแหน่งที่ถูกต้องของ List ที่เรียงแล้ว ([8])
ผลลัพธ์: [7, 8, 2, 1, 4, 9, 3, 5, 0, 6]
รอบที่ 2:
นำ 2 มาแทรกในตำแหน่งที่ถูกต้องของ List ที่เรียงแล้ว ([7, 8])
ผลลัพธ์: [2, 7, 8, 1, 4, 9, 3, 5, 0, 6]
ทำซ้ำจนครบทุกรอบ:
ในแต่ละรอบจะนำข้อมูลมาแทรกในตำแหน่งที่ถูกต้องของ List ที่เรียงแล้ว
ผลลัพธ์สุดท้าย: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
สรุป
Bubble Sort: เปรียบเทียบและสลับค่าข้อมูลที่อยู่ติดกันไปเรื่อยๆ
Selection Sort: หาค่าน้อยสุดและสลับกับตำแหน่งปัจจุบัน
Insertion Sort: นำข้อมูลแต่ละตัวไปแทรกในตำแหน่งที่เหมาะสมใน List ที่เรียงแล้ว
ทั้งสามอัลกอริทึมใช้เวลา O(n²) ในกรณี worst-case แต่ Insertion Sort มีประสิทธิภาพดีกว่าในกรณีที่ข้อมูลเกือบเรียงลำดับแล้ว