Chủ đề Fcs : Giải quyết vấn đề với sự trợ giúp của máy tính – Kĩ thuật lập trình – Bài 9. Lập trình thuật toán sắp xếp nhanh – sách giáo khoa trang 127 lớp 11 Khoa học máy tính – Cánh Diều, mời các em tham khảo cùng Bumbii.
Chủ đề Fcs : Giải quyết vấn đề với sự trợ giúp của máy tính – Bài 9. Lập trình thuật toán sắp xếp nhanh
KHỞI ĐỘNG
Nếu cần chọn một trong hai việc sau đây, em sẽ chọn việc làm nào? Vì sao?
1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.
2) Từ chương trình Python thực hiện thuật toán, viết lại ngắn gọn ý tưởng chính của thuật toán.
Hướng dẫn lời giải:
Câu hỏi khởi động đề cập đến lựa chọn bài toán xuôi hay bài toán ngược. Thường thì bài toán ngược khó hơn khi mà thuật toán cuối cùng đã qua các bước cải tiến, trở nên tinh tế trong các chi tiết, rất khó hiểu ý tưởng chính là gì. Chỉ với thuật toán thô, dựa trên ý tưởng ban đầu đơn giản thì bài toán ngược không khó hơn bài toán xuôi.
THỰC HÀNH
Nhiệm vụ 1
Viết chương trình thực hiện sắp xếp nhanh một dãy số và chạy thử kiểm tra.
a) Dựa trên mã lệnh thuật toán cho trong Hình 3.
b) Dựa trên mã lệnh thuật toán cho trong Hình 5.
Lời giải:
a) Mã lệnh sử dụng phân đoạn Lomuto:
def PhanDoanLomuto(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(arr, low, high):
if low < high:
pi = PhanDoanLomuto(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
if __name__ == "__main__":
# Một mảng ví dụ
unsorted_array = [64, 34, 25, 12, 22, 11, 90]
print("Mảng chưa sắp xếp:", unsorted_array)
# Gọi hàm sắp xếp
quickSort(unsorted_array, 0, len(unsorted_array) - 1)
print("Mảng đã sắp xếp:", unsorted_array)b) Mã lệnh sử dụng phân đoạn Hoare:
def hoarePartition(arr, low, high):
pivot = arr[low]
i = low - 1
j = high + 1
while True:
while True:
i += 1
if arr[i] >= pivot:
break
while True:
j -= 1
if arr[j] <= pivot:
break
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quickSortHoare(arr, low, high):
if low < high:
pi = hoarePartition(arr, low, high)
quickSortHoare(arr, low, pi)
quickSortHoare(arr, pi + 1, high)
if __name__ == "__main__":
unsorted_array = [64, 34, 25, 12, 22, 11, 90]
print("Mảng chưa sắp xếp:", unsorted_array)
quickSortHoare(unsorted_array, 0, len(unsorted_array) - 1)
print("Mảng đã sắp xếp:", unsorted_array)Nhiệm vụ 2
Bổ sung thêm các câu lệnh in kết quả trung gian vào các chương trình nói trên để có thể quan sát diễn biến từng bước thực hiện sắp xếp nhanh một dãy số.
Lời giải:
Mã lệnh sử dụng phân đoạn Lomuto:
def PhanDoanLomuto(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(arr, low, high):
if low < high:
print(arr) #in mảng arr sau mỗi lần sắp xếp
pi = PhanDoanLomuto(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
if __name__ == "__main__":
# Một mảng ví dụ
unsorted_array = [64, 34, 25, 12, 22, 11, 90]
print("Mảng chưa sắp xếp:", unsorted_array)
# Gọi hàm sắp xếp
quickSort(unsorted_array, 0, len(unsorted_array) - 1)
print("Mảng đã sắp xếp:", unsorted_array)Mã lệnh sử dụng phân đoạn Hoare:
def hoarePartition(arr, low, high):
pivot = arr[low]
i = low - 1
j = high + 1
while True:
while True:
i += 1
if arr[i] >= pivot:
break
while True:
j -= 1
if arr[j] <= pivot:
break
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quickSortHoare(arr, low, high):
if low < high:
print(arr) #in mảng arr sau mỗi lần sắp xếp
pi = hoarePartition(arr, low, high)
quickSortHoare(arr, low, pi)
quickSortHoare(arr, pi + 1, high)
if __name__ == "__main__":
unsorted_array = [64, 34, 25, 12, 22, 11, 90]
print("Mảng chưa sắp xếp:", unsorted_array)
quickSortHoare(unsorted_array, 0, len(unsorted_array) - 1)
print("Mảng đã sắp xếp:", unsorted_array)VẬN DỤNG
Em hãy thực hiện các công việc sau:
a) Sửa lại thủ tục phân đoạn đề có hàm quickSort_down sắp xếp theo thứ tự giảm dần.
Gợi ý: Sửa đối phép so sánh trong câu lệnh if a[j] <= pivot: thành if a[j] >= pivot:
b) Tiếp tục sửa lại để có hàm quickSort_tuple_down sắp xếp danh sách các cặp, ví dụ (tên học sinh, điểm môn học) theo điệm môn học giảm dần.
Gợi ý: Sửa đổi đầu vào thành danh sách các cặp (tên học sinh, điểm môn học) và thực hiện so sánh theo điểm môn học.
Lời giải:
a)
def PhanDoanLomuto_down(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] >= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1b)
Truy cập giá trị điểm môn học bằng hai số. Chỉ số hàng i ứng với HS thứ i, chỉ số cột k = 1 ứng với cột điểm môn học.
Phép gán trị cho pivot:
pivot = a[hi] đổi thành pivot = a[hi][1]
Phéo so sánh trong câu lệnh kiểm tra:
if arr[j]>= pivot: đổi thành if arr[j][1] >= pivot:
def PhanDoanLomuto_down(arr, low, high):
pivot = arr[high][1]
i = low - 1
for j in range(low, high):
if arr[j][1] >= pivot:
...CÂU HỎI
Câu 1. Em hãy giải thích tại sao lại nói: Thuật toán sắp xếp nhanh (QuickSort) theo chiến lược “chia đề trị”.
Lời giải:
Thuật toán sắp xếp nhanh (QuickSort) theo chiến lược “chia đề trị” vì:
- Phân đoạn là chia dãy số làm hai phần.
- Thuật toán sắp xếp nhanh thực hiện bởi một hàm đệ quy gọi thực hiện việc phân đoạn nhiều lần cho đến khi mỗi đoạn con chỉ còn là một số.
Câu 2. Theo em thì diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ giống hay sẽ khác với dùng phân đoạn Hoare?
Lời giải:
Theo em, diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ khác trong các bước đổi chỗ để phân đoạn với dùng phân đoạn Hoare.
Xem các bài giải khác: Giải Bài Tập Sách Giáo Khoa Tin Học Lớp 11 Khoa Học Máy Tính – Cánh Diều
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
