Hướng dẫn giải (?) Câu hỏi mục 4 NV1 Bài 8. Lập trình một số thuật toán sắp xếp (trang 122, 123, 124) – SGK Tin học 11 Cánh diều. Hướng dẫn: Dựa vào kiến thức đã học và kỹ năng lập trình.
Câu hỏi/Đề bài:
Em hãy thực hiện các công việc sau:
a) Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.
b) Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.
c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính.
Hướng dẫn:
Dựa vào kiến thức đã học và kỹ năng lập trình.
Lời giải:
a) Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính, sử dụng vòng lặp:
for i in range (1, n):
val ai
k i – 1
b) Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính, sử dụng các câu lệnh:
while k >= 0 and ak > val:
ak+1 ak
k k-1
ak+1 val
c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính:
Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước.
Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1.