HomeLập trìnhPythonCách sắp xếp...

Cách sắp xếp danh sách theo cách đệ quy trong Python


Khi bạn muốn sắp xếp một danh sách hoặc mảng trong Python, có nhiều thuật toán sắp xếp mà bạn có thể sử dụng.

Một số sử dụng các khái niệm vòng lặp như Sắp xếp chèn, Sắp xếp bong bóng và Sắp xếp lựa chọn. Mặt khác, bạn cũng có thể sắp xếp cùng một danh sách hoặc mảng bằng cách sử dụng Hợp nhất Sắp xếp với sự trợ giúp của đệ quy.

Trong bài viết này, bạn sẽ tìm hiểu cách thức hoạt động của thuật toán Sắp xếp hợp nhất. Bạn cũng sẽ tìm hiểu xem đệ quy đóng vai trò quan trọng như thế nào trong Sắp xếp Hợp nhất.

Cách thức hoạt động của đệ quy

Như một điều kiện tiên quyết, trước tiên chúng ta sẽ hiểu cách thức hoạt động của đệ quy, vì nó là xương sống của thuật toán sắp xếp hợp nhất.

Đầu tiên, bạn nên biết rằng hàm đệ quy là hàm gọi chính nó cho đến khi nó đạt được kết quả mong muốn.

Bây giờ, trừ khi bạn đặt một số điều kiện để dừng quá trình này, nó sẽ tiếp tục mãi mãi – hoặc cho đến khi mã JS của bạn báo lỗi. Đây được gọi là trường hợp cơ sở và nó sẽ ngăn chức năng tự gọi khi điều kiện của nó được đáp ứng.

Bây giờ bạn đã biết những kiến ​​thức cơ bản về đệ quy, hãy tìm hiểu kỹ hơn một chút và hiểu cách thức hoạt động của nó:

Nói chung, đệ quy hoạt động dựa trên một khái niệm gọi là Quy nạp toán học chính (PMI). Nói một cách đơn giản, PMI là một kỹ thuật được sử dụng để chứng minh một số nhận định nhất định từ một tập hợp cơ bản các nhận định đã được chứng minh.

Thông thường, có ba bước trong quy trình này.

Hãy chứng minh công thức của n số tự nhiên là P(n)= n*(n+1)/2 sử dụng PMI:

123
Để chứng minh rằng P(n) đúng

Bước 1: Bước đầu tiên còn được gọi là trường hợp cơ sở. Trong bước này, bạn chỉ định các tuyên bố đã được chứng minh. Thông thường, chúng ta biết rằng tổng của 1 số tự nhiên đầu tiên là 1. Hãy coi nó là vế trái của phương trình (LHS).

Đọc thêm  Tìm hiểu đánh máy bằng Python trong năm phút

Khi chúng tôi áp dụng n = 1 trong công thức, chúng tôi nhận được p(1) = 1*(1+1)/2 => 1 như vế phải (RHS).

1234
Áp dụng 1 trong công thức

Điều này có nghĩa là LHS = RHS. Bước này xác nhận đó là trường hợp cơ sở hợp lệ.

Bước 2: Bước này được gọi là Giả thuyết cảm ứng. Trong bước này, chúng ta chỉ đơn giản giả sử rằng công thức này đúng với một số nguyên k ở đâu 1 < k < n. Vì vậy, chúng tôi thay thế k trong công thức và chúng tôi nhận được p(k) = k*(k+1)/2:

12345
Bước giả thuyết cảm ứng cho một số giá trị nguyên k

Bước 3: Bước này được gọi là bước quy nạp. Tại thời điểm này, chúng ta phải chứng minh rằng điều này sẽ đúng với số nguyên k+1.

Khi chúng ta thay thế k + 1 vào công thức và coi đó là LHS thì ta được như sau:

125
Tuyên bố LHS cho P(k+1)

Đối với RHS, chúng ta biết rằng tổng của số tự nhiên k+1 số nguyên bằng tổng các số tự nhiên k số nguyên và k+1số nguyên. Chúng ta có thể viết nó như thế này:

21
Tổng của k+1 số nguyên bằng (k+1)số nguyên và tổng của k số nguyên

Phương trình trên có thể được viết lại như sau:

22
tổng của k số nguyên tự nhiên được viết lại thành p(k) từ bước 2

Tại thời điểm này, chúng ta biết giá trị của p(k) từ bước 2 (Giả thuyết Quy nạp). Khi chúng tôi thay thế giá trị của p(k), chúng tôi nhận được điều này:

23
Thay p(k) từ bước 2

Chúng ta có thể lấy mẫu số chung và đơn giản hóa phương trình, và chúng ta nhận được:

37
Đơn giản hóa phương trình

Khi so sánh LHS và RHS, chúng tôi nhận được kết quả tương tự và chúng tôi đã chứng minh rằng công thức này hoạt động cho k+1 số nguyên.

Ngoài ra, khi chúng ta thay thế n ở nơi k+1chúng tôi nhận được kết quả cuối cùng là:

45
Thay k+1 bằng n

Ta đã chứng minh được công thức của n số tự nhiên là n*(n+1)/2.

Khi chúng tôi quan sát tất cả các bước trong PMI, chúng tôi đã thực hiện một giả định đơn giản ở bước 2 và do đó, chúng tôi đã chứng minh tuyên bố ở bước 3.

Đây là cách đệ quy hoạt động: chúng tôi khởi tạo một trường hợp cơ sở cho một vấn đề khi bắt đầu hàm và chúng tôi giả định rằng hàm này hoạt động với các giá trị nhỏ của cùng một vấn đề. Sau đó, là bước cuối cùng, chúng tôi chứng minh rằng điều này hoạt động cho vấn đề hiện có.

Cách hoạt động của thuật toán sắp xếp hợp nhất

Thuật toán Sắp xếp Hợp nhất hoạt động bằng cách chia nhỏ danh sách chưa được sắp xếp thành hai nửa. Sau đó, bạn gọi sắp xếp hợp nhất trên từng phần trong số hai phần này.

Đọc thêm  Google Colaboratory – Cách chạy mã Python trong Google Drive của bạn

Vì, chúng tôi biết đệ quy hoạt động dựa trên Quy nạp toán học chính (PMI), chúng tôi giả định rằng các danh sách nhỏ hơn được sắp xếp khi gọi sắp xếp hợp nhất trên 2 danh sách nhỏ hơn này.

Ghi chú: Trước khi gọi đệ quy trong các danh sách nhỏ hơn, điều quan trọng hơn là xác định trường hợp cơ sở cho hàm vì nó đóng vai trò là điểm dừng cho lệnh gọi đệ quy.

Ở đây, trường hợp cơ sở để sắp xếp hợp nhất sẽ là nếu độ dài của danh sách là 1. Trong trường hợp đó (nếu độ dài là 1, nghĩa là chỉ có một mục trong danh sách), danh sách đã được sắp xếp nên chúng ta phải chỉ cần trả lại danh sách như nó là.

Để rõ ràng hơn, hãy lấy một ví dụ và triển khai sắp xếp hợp nhất trên danh sách chưa sắp xếp.

my_list = [3,8,2,7,1,4,5] 
danh sách chưa sắp xếp

Trong đoạn mã trên, bạn có thể thấy rằng biến my_list chứa một danh sách chưa được sắp xếp.

Bây giờ, vì độ dài của my_list không phải là 1, nên chúng ta không thể cho rằng nó đã được sắp xếp. Vì vậy, chúng tôi gọi sắp xếp hợp nhất trên nửa đầu list1 = [3,8,2] và cũng gọi sắp xếp hợp nhất vào nửa sau list2 = [7,1,4,5].

Chúng tôi cho rằng list1list2 được sắp xếp theo bước quy nạp. Bây giờ, danh sách trông giống như list1 = [2,3,8]list2 = [1,4,5,7]. Bây giờ, tất cả những gì chúng ta phải làm là hợp nhất hai danh sách đã sắp xếp đó thành một danh sách bằng cách sử dụng kỹ thuật hai con trỏ.

Để kết hợp và sắp xếp hai danh sách được sắp xếp nhỏ hơn, chúng tôi lấy 2 con trỏ, trỏ vào đầu mỗi danh sách.

56
Con trỏ tại chỉ mục bắt đầu của danh sách và danh sách trống để nối thêm danh sách mới trong khi so sánh
333
Bước trung gian trong quá trình so sánh giá trị con trỏ

Chúng tôi đang so sánh giá trị tại mỗi vị trí mà con trỏ trỏ đến và bất kỳ giá trị nào nhỏ hơn, chúng tôi sẽ thêm giá trị đó vào danh sách cuối cùng. Sau đó, chúng tôi di chuyển vị trí con trỏ đến chỉ mục tiếp theo.

Sau khi lặp qua quá trình này, khi chúng tôi đạt đến chỉ mục cuối cùng đầu tiên (ở một trong hai vòng lặp mà chúng tôi đang tham gia), chúng tôi sẽ dừng vòng lặp. Sau đó, chúng tôi nối tất cả các giá trị trong danh sách khác (nếu còn lại) vào danh sách cuối cùng.

Đọc thêm  Liệt kê mức độ hiểu trong Python được giải thích cho người mới bắt đầu

Sử dụng kỹ thuật này, chúng ta có thể hợp nhất và sắp xếp hai danh sách nhỏ đã được sắp xếp trước.

Sơ đồ trống--1-
Quy trình làm việc của sắp xếp hợp nhất

Khi chúng tôi đang sử dụng đệ quy, chúng tôi cho rằng nó hoạt động khi chúng tôi gọi cùng một chức năng cho một vấn đề nhỏ hơn. Giả định này xuất phát từ bước giả thuyết cảm ứng trong PMI.

Vì vậy, khi chúng ta khai báo trường hợp cơ sở cho vấn đề, tương tự như vậy, chúng ta giả định rằng hàm sẽ trả về câu trả lời đúng cho các vấn đề nhỏ hơn. Tất cả những gì chúng ta phải làm là chứng minh rằng điều này cũng đúng với những bài toán lớn hơn.

Trong thuật toán này, chúng tôi đã tuyên bố rằng trường hợp cơ sở là đối với độ dài danh sách là 1, danh sách được sắp xếp. Trong bước giả thuyết quy nạp, chúng tôi giả định rằng thuật toán sẽ hoạt động cho một nửa danh sách. Trong bước thứ ba, chúng tôi chỉ hợp nhất danh sách đã sắp xếp và chứng minh rằng điều này sẽ hoạt động trên một danh sách lớn hơn.

Mã Python cho thuật toán sắp xếp hợp nhất

def merge_sort(my_list):

	# Base Case
    if len(my_list) <= 1:
        return my_list
   
    list_1 = my_list[0:len(my_list) // 2]
    list_2 = my_list[len(my_list) // 2:]
    
   	# Induction Step
    ans_1 = merge_sort(list_1)
    ans_2 = merge_sort(list_2)
    
    # Sorting and merging two sorted list
    sort_list = sort_two_list(ans_1, ans_2)
    return sort_list



# Separate Function to sort and merge 2 sorted lists
def sort_two_list(list_1, list_2):
    final_list = []
    i = 0
    j = 0
    while i < len(list_1) and j < len(list_2):
        if list_1[i] <= list_2[j]:
            final_list.append(list_1[i])
            i += 1
            continue
        final_list.append(list_2[j])
        j += 1

    while i < len(list_1):
        final_list.append(list_1[i])
        i = i + 1
        
    while j < len(list_2):
        final_list.append(list_2[j])
        j = j + 1
        
    return final_list


my_list = [3, 8, 2, 7, 1, 4, 5]
ans = merge_sort(my_list)
print(ans)
# prints [1, 2, 3, 4, 5, 7, 8]
Triển khai thuật toán sắp xếp hợp nhất trong Python

Như bạn thấy trong đoạn mã trên, tôi đã triển khai hai chức năng riêng biệt để sắp xếp và hợp nhất hai danh sách đã sắp xếp. Điều này dẫn đến khả năng đọc tốt hơn và đánh giá mã dễ dàng hơn.

Hạn chế chính trong sắp xếp hợp nhất là nó sử dụng nhiều không gian hơn. Điều này là do, tại mỗi cuộc gọi đệ quy, một danh sách mới được tạo và đệ quy được gọi trên danh sách mới đó. Vì vậy, độ phức tạp không gian cho trường hợp xấu nhất là O(n) và độ phức tạp thời gian là O(n log n).

Phần kết luận

Hợp nhất Sắp xếp khá nhanh trong việc sắp xếp danh sách theo cách đệ quy từ góc độ phức tạp về thời gian. Điều này rất hữu ích để đếm các đảo ngược trong danh sách và nó được sử dụng rộng rãi cho các ứng dụng sắp xếp bên ngoài hơn các thuật toán sắp xếp khác.

Chúc lập trình vui vẻ…



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status