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

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

Trả lờ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.