Sắp xếp chèn dùng đệ quy

Cần sắp xếp A[0] tới A[k] theo thứ tự không giảm. Khi k≤0, phần đang xét có không quá một phần tử nên không cần chèn. Khi k>0, trước hết gọi cùng hàm để sắp xếp A[0] tới A[k−1], rồi chèn A[k] vào phần đầu đã có thứ tự. ```python def sap_xep_chen(A, k): if k <= 0: return sap_xep_chen(A, k - 1) value = A[k] j = k - 1 while j >= 0 and A[j] > value: A[j + 1] = A[j] j -= 1 A[j + 1] = value ``` Gọi ban đầu sap_xep_chen(A,len(A)−1). Hàm dùng đệ quy cho phần đầu; vòng while vẫn dùng để dời các phần tử lớn hơn value sang phải.

Tải mã Python mẫu, mở bằng trình soạn thảo đã dùng và chạy với Python3. Mẫu chọn n từ 0 đến20 để các lời gọi tính trực tiếp nhỏ; đây là giới hạn thử, không phải giới hạn toán học. Với n=4, cần nhận tổng10, tổng lẻ4, giai thừa24, 3^n=81 và tổng giai thừa33. Dãy mẫu [9,4,7,4] được in ngược thành4,7,4,9, rồi sau sắp xếp thành [4,4,7,9]; tìm 7 trả chỉ số 2. Với n=0, tổng/tổng lẻ/tổng giai thừa bằng 0, giai thừa và 3^n bằng 1. Nhập chữ hoặc n âm phải được báo dữ liệu không phù hợp trước phần tính số. Khi thử riêng hàm dãy, thêm trường hợp rỗng, một phần tử, đã sắp xếp, thứ tự giảm và phần tử trùng. Kiểm dãy sau sắp xếp và kết quả tìm kiếm, không chỉ nhìn chương trình kết thúc.