Chúng ta đã biết thuật toán sắp xếp chèn trên dãy A cho trước theo hàm sau

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 2: Thiết kế thuật toán đệ quy

Vận dụng 2 trang 15 Chuyên đề Tin học 11:Chúng ta đã biết thuật toán sắp xếp chèn trên dãy A cho trước theo hàm sau

Hãy thiết kế lại chương trình trên sử dụng kĩ thuật đệ quy

Lời giải:

Để sắp xếp một mảng bằng thuật toán sắp xếp chèn đệ quy, ta có thể thực hiện theo thuật toán sau:

1. Kiểm tra điều kiện dừng: nếu độ dài của mảng là 1 hoặc ít hơn, mảng đã được sắp xếp.

2. Trường hợp ngược lại, sắp xếp mảng con trừ phần tử cuối cùng (arr[:-1]) bằng thuật toán sắp xếp chèn đệ quy.

3. Chèn phần tử cuối cùng vào mảng con đã sắp xếp được trả về ở bước 2.