Làm thế nào để bạn viết một thuật toán trong python?

Thời gian mã của bạn

Khi so sánh hai thuật toán sắp xếp trong Python, sẽ luôn hữu ích khi xem mỗi thuật toán chạy trong bao lâu. Thời gian cụ thể mà mỗi thuật toán sử dụng sẽ được xác định một phần bởi phần cứng của bạn, nhưng bạn vẫn có thể sử dụng thời gian tỷ lệ thuận giữa các lần thực thi để giúp bạn quyết định cách triển khai nào hiệu quả hơn về thời gian

Trong phần này, bạn sẽ tập trung vào một cách thực tế để đo thời gian thực cần thiết để chạy các thuật toán sắp xếp của bạn bằng cách sử dụng mô-đun

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Đây là một hàm bạn có thể sử dụng để tính thời gian cho các thuật toán của mình

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

Trong ví dụ này,

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

• Dòng 8 nhập tên của thuật toán bằng phép thuật chuỗi f của Python. Điều này là để

  $ python sorting.py
  Algorithm: sorted. Minimum execution time: 0.010945824000000007
  

  1 biết gọi thuật toán từ đâu. Lưu ý rằng điều này chỉ cần thiết cho việc triển khai tùy chỉnh được sử dụng trong hướng dẫn này. Nếu thuật toán được chỉ định là

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  6 tích hợp, thì sẽ không có gì được nhập

• Dòng 11 chuẩn bị gọi thuật toán với mảng được cung cấp. Đây là câu lệnh sẽ được thực thi và tính thời gian

• Dòng 15 gọi

  $ python sorting.py
  Algorithm: sorted. Minimum execution time: 0.010945824000000007
  

  1 với mã thiết lập và câu lệnh. Thao tác này sẽ gọi thuật toán sắp xếp đã chỉ định mười lần, trả về số giây mà mỗi lần thực hiện này đã thực hiện

• Dòng 19 xác định thời gian ngắn nhất được trả về và in nó cùng với tên của thuật toán

Ghi chú. Một quan niệm sai lầm phổ biến là bạn nên tìm thời gian trung bình của mỗi lần chạy thuật toán thay vì chọn thời gian ngắn nhất. Các phép đo thời gian bị nhiễu vì hệ thống chạy đồng thời các quy trình khác. Thời gian ngắn nhất luôn ít nhiễu nhất, giúp nó thể hiện tốt nhất thời gian chạy thực của thuật toán

Đây là một ví dụ về cách sử dụng

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Nếu bạn lưu đoạn mã trên vào tệp

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

Hãy nhớ rằng thời gian tính bằng giây của mọi thử nghiệm phụ thuộc một phần vào phần cứng bạn sử dụng, do đó, bạn có thể sẽ thấy kết quả hơi khác khi chạy mã

Ghi chú. Bạn có thể tìm hiểu thêm về mô-đun

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Đo lường hiệu quả với ký hiệu Big O

Thời gian cụ thể mà một thuật toán cần để chạy không đủ thông tin để có được bức tranh đầy đủ về độ phức tạp về thời gian của nó. Để giải quyết vấn đề này, bạn có thể sử dụng ký hiệu Big O (phát âm là “big oh”). Big O thường được sử dụng để so sánh các cách triển khai khác nhau và quyết định cách triển khai nào hiệu quả nhất, bỏ qua các chi tiết không cần thiết và tập trung vào điều quan trọng nhất trong thời gian chạy của thuật toán

Thời gian tính bằng giây cần thiết để chạy các thuật toán khác nhau có thể bị ảnh hưởng bởi một số yếu tố không liên quan, bao gồm tốc độ bộ xử lý hoặc bộ nhớ khả dụng. Mặt khác, Big O cung cấp một nền tảng để thể hiện độ phức tạp của thời gian chạy theo thuật ngữ bất khả tri về phần cứng. Với Big O, bạn thể hiện độ phức tạp theo thời gian chạy thuật toán của bạn tăng nhanh như thế nào so với kích thước của đầu vào, đặc biệt là khi đầu vào tăng lớn tùy ý

Giả sử rằng n là kích thước của đầu vào cho một thuật toán, ký hiệu Big O biểu thị mối quan hệ giữa n và số bước mà thuật toán thực hiện để tìm giải pháp. Big O sử dụng chữ in hoa “O” theo sau là mối quan hệ này bên trong dấu ngoặc đơn. Ví dụ: O(n) đại diện cho các thuật toán thực hiện một số bước tỷ lệ với kích thước đầu vào của chúng

Mặc dù hướng dẫn này sẽ không đi sâu vào chi tiết của ký hiệu Big O, đây là năm ví dụ về độ phức tạp thời gian chạy của các thuật toán khác nhau

Big OComplexityDescriptionO(1)constantThời gian chạy không đổi bất kể kích thước của đầu vào. Tìm một phần tử trong bảng băm là một ví dụ về thao tác có thể được thực hiện trong thời gian không đổi. O(n)linearThời gian chạy phát triển tuyến tính với kích thước của đầu vào. Hàm kiểm tra một điều kiện trên mọi mục của danh sách là một ví dụ về thuật toán O(n). O(n2)quadraticThời gian chạy là một hàm bậc hai của kích thước đầu vào. Một triển khai ngây thơ của việc tìm các giá trị trùng lặp trong một danh sách, trong đó mỗi mục phải được kiểm tra hai lần, là một ví dụ về thuật toán bậc hai. O(2n)exponentialThời gian chạy tăng theo cấp số nhân với kích thước của đầu vào. Các thuật toán này được coi là cực kỳ kém hiệu quả. Một ví dụ về thuật toán hàm mũ là bài toán ba màu. O(log n)logaritThời gian chạy tăng tuyến tính trong khi kích thước của đầu vào tăng theo cấp số nhân. Ví dụ: nếu mất một giây để xử lý một nghìn phần tử, thì sẽ mất hai giây để xử lý mười nghìn, ba giây để xử lý một trăm nghìn, v.v. Tìm kiếm nhị phân là một ví dụ về thuật toán thời gian chạy logarit

Hướng dẫn này bao gồm độ phức tạp thời gian chạy Big O của từng thuật toán sắp xếp được thảo luận. Nó cũng bao gồm một lời giải thích ngắn gọn về cách xác định thời gian chạy trên từng trường hợp cụ thể. Điều này sẽ giúp bạn hiểu rõ hơn về cách bắt đầu sử dụng Big O để phân loại các thuật toán khác

Ghi chú. Để hiểu sâu hơn về Big O, cùng với một số ví dụ thực tế trong Python, hãy xem Ký hiệu Big O và Phân tích thuật toán với các ví dụ về Python

Triển khai Sắp xếp bong bóng trong Python

Đây là cách triển khai thuật toán sắp xếp bong bóng trong Python

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Vì cách triển khai này sắp xếp mảng theo thứ tự tăng dần, nên mỗi bước sẽ “xếp bong bóng” phần tử lớn nhất vào cuối mảng. Điều này có nghĩa là mỗi lần lặp mất ít bước hơn so với lần lặp trước vì phần lớn hơn liên tục của mảng được sắp xếp

Các vòng lặp ở dòng 4 và 10 xác định cách thuật toán chạy qua danh sách. Lưu ý cách ban đầu

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

Khi các vòng lặp tiến triển, dòng 15 so sánh từng phần tử với giá trị liền kề của nó và dòng 18 hoán đổi chúng nếu chúng không đúng thứ tự. Điều này đảm bảo một danh sách được sắp xếp ở cuối hàm

Ghi chú. Cờ

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Như một bài tập, bạn có thể loại bỏ việc sử dụng cờ này và so sánh thời gian chạy của cả hai cách triển khai

Để phân tích chính xác cách thức hoạt động của thuật toán, hãy xem xét một danh sách có giá trị

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Bây giờ hãy xem từng bước điều gì đang xảy ra với mảng khi thuật toán tiến triển

1. Mã bắt đầu bằng cách so sánh phần tử đầu tiên,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   73, với phần tử liền kề của nó,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   74. Kể từ

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   75, các giá trị được hoán đổi, dẫn đến thứ tự sau.

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   76

2. Sau đó, thuật toán so sánh phần tử thứ hai,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   73, với phần tử liền kề của nó,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   78. Kể từ

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   79, các giá trị được hoán đổi, dẫn đến thứ tự sau.

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   00

3. Tiếp theo, thuật toán so sánh phần tử thứ ba,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   73, với phần tử liền kề của nó,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   02. Kể từ

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   03, nó cũng hoán đổi các giá trị, dẫn đến thứ tự sau.

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   04

4. Cuối cùng, thuật toán so sánh phần tử thứ tư,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   73, với phần tử liền kề của nó,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   06 và hoán đổi chúng, kết quả là

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   07. Tại thời điểm này, thuật toán đã hoàn thành bước đầu tiên thông qua danh sách (

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   08). Lưu ý cách giá trị

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   73 tăng vọt từ vị trí ban đầu đến đúng vị trí của nó ở cuối danh sách

5. Pass thứ hai (

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   00) tính đến việc phần tử cuối cùng của danh sách đã được định vị và tập trung vào bốn phần tử còn lại,

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   01. Khi kết thúc lần vượt qua này, giá trị

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   78 tìm thấy đúng vị trí của nó. Lần thứ ba đi qua danh sách định vị giá trị

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   06, v.v. cho đến khi danh sách được sắp xếp

Đo độ phức tạp thời gian chạy Big O của Bubble Sort

Việc triển khai sắp xếp bong bóng của bạn bao gồm hai vòng lặp

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Trước đó, bạn đã biết rằng Big O tập trung vào cách thời gian chạy phát triển so với kích thước của đầu vào. Điều đó có nghĩa là, để biến phương trình trên thành độ phức tạp Big O của thuật toán, bạn cần loại bỏ các hằng số vì chúng không thay đổi theo kích thước đầu vào

Làm như vậy sẽ đơn giản hóa ký hiệu thành n2 - n. Vì n2 tăng nhanh hơn nhiều so với n, nên số hạng cuối cùng này cũng có thể bị loại bỏ, để lại sắp xếp bong bóng với độ phức tạp trung bình và trường hợp xấu nhất là O(n2)

Trong trường hợp thuật toán nhận được một mảng đã được sắp xếp—và giả sử việc triển khai bao gồm tối ưu hóa cờ

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Khi đó, O(n) là độ phức tạp thời gian chạy trường hợp tốt nhất của sắp xếp bong bóng. Nhưng hãy nhớ rằng các trường hợp tốt nhất là một ngoại lệ và bạn nên tập trung vào trường hợp trung bình khi so sánh các thuật toán khác nhau

Thời gian thực hiện sắp xếp bong bóng của bạn

Sử dụng

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Bây giờ bạn có thể chạy tập lệnh để nhận thời gian thực hiện của

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Mất 408 giây để sắp xếp mảng có mười nghìn phần tử. Điều này đại diện cho việc thực hiện nhanh nhất trong số mười lần lặp lại mà

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

Ghi chú. Một lần thực hiện sắp xếp bong bóng mất

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Phân tích điểm mạnh và điểm yếu của sắp xếp bong bóng

Ưu điểm chính của thuật toán sắp xếp bong bóng là tính đơn giản của nó. Thật đơn giản để thực hiện và hiểu. Đây có lẽ là lý do chính tại sao hầu hết các khóa học khoa học máy tính đều giới thiệu chủ đề sắp xếp bằng cách sử dụng sắp xếp bong bóng

Như bạn đã thấy trước đây, nhược điểm của sắp xếp bong bóng là nó chậm, với độ phức tạp thời gian chạy là O(n2). Thật không may, điều này loại trừ nó như một ứng cử viên thực tế để sắp xếp các mảng lớn

Triển khai Sắp xếp chèn trong Python

Thuật toán sắp xếp chèn hoạt động chính xác như ví dụ với cỗ bài. Đây là cách triển khai trong Python

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Không giống như sắp xếp bong bóng, việc triển khai sắp xếp chèn này xây dựng danh sách được sắp xếp bằng cách đẩy các mục nhỏ hơn sang trái. Hãy chia nhỏ

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

• Dòng 4 thiết lập vòng lặp xác định

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  44 mà hàm sẽ định vị trong mỗi lần lặp. Lưu ý rằng vòng lặp bắt đầu với mục thứ hai trong danh sách và đi đến mục cuối cùng

• Dòng 7 khởi tạo

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  44 với mục mà hàm đang cố đặt

• Dòng 12 khởi tạo một biến sẽ liên tiếp trỏ đến từng phần tử bên trái của

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  46. Đây là những yếu tố sẽ được so sánh liên tiếp với

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  44

• Dòng 18 so sánh

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  44 với từng giá trị ở bên trái của nó bằng cách sử dụng vòng lặp

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  49, dịch chuyển các phần tử để nhường chỗ cho vị trí của

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  44

• Dòng 27 đặt

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  44 vào đúng vị trí của nó sau khi thuật toán dịch chuyển tất cả các giá trị lớn hơn sang bên phải

Đây là hình minh họa các lần lặp lại khác nhau của thuật toán khi sắp xếp mảng

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Bây giờ đây là tóm tắt các bước của thuật toán khi sắp xếp mảng

1. Thuật toán bắt đầu với

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   63 và đi qua mảng con bên trái của nó để tìm vị trí chính xác cho nó. Trong trường hợp này, mảng con là

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   64

2. Kể từ

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   65, thuật toán dịch chuyển phần tử

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   73 sang phải một vị trí. Mảng kết quả tại thời điểm này là

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   67

3. Vì không còn phần tử nào trong mảng con, nên giờ đây

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   44 được đặt ở vị trí mới và mảng cuối cùng là

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   76

4. Đường truyền thứ hai bắt đầu bằng ________ 730 và đi qua dãy con nằm ở bên trái của nó, trong trường hợp này là ________ 731

5. Kể từ

   $ python sorting.py
   Algorithm: sorted. Minimum execution time: 0.010945824000000007
   

   32, thuật toán dịch chuyển 8 sang phải. Mảng kết quả tại thời điểm này là

   $ python sorting.py
   Algorithm: sorted. Minimum execution time: 0.010945824000000007
   

   33

6. Kể từ

   $ python sorting.py
   Algorithm: sorted. Minimum execution time: 0.010945824000000007
   

   34, thuật toán không cần tiếp tục đi qua mảng con, do đó, nó định vị

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   44 và kết thúc lượt thứ hai. Tại thời điểm này, mảng kết quả là

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   00

7. Lần thứ ba đi qua danh sách đặt phần tử

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   02 vào đúng vị trí của nó và lần thứ tư đặt phần tử

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   06 vào đúng vị trí, để mảng được sắp xếp

Đo độ phức tạp thời gian chạy Big O của Sắp xếp chèn

Tương tự như cách triển khai sắp xếp bong bóng của bạn, thuật toán sắp xếp chèn có một vài vòng lặp lồng nhau đi qua danh sách. Vòng lặp bên trong khá hiệu quả vì nó chỉ đi qua danh sách cho đến khi tìm thấy đúng vị trí của một phần tử. Điều đó nói rằng, thuật toán vẫn có độ phức tạp thời gian chạy O(n2) trong trường hợp trung bình

Trường hợp xấu nhất xảy ra khi mảng được cung cấp được sắp xếp theo thứ tự ngược lại. Trong trường hợp này, vòng lặp bên trong phải thực hiện mọi phép so sánh để đặt mọi phần tử vào đúng vị trí của nó. Điều này vẫn mang lại cho bạn độ phức tạp thời gian chạy O(n2)

Trường hợp tốt nhất xảy ra khi mảng được cung cấp đã được sắp xếp. Ở đây, vòng lặp bên trong không bao giờ được thực thi, dẫn đến độ phức tạp thời gian chạy O(n), giống như trường hợp tốt nhất của sắp xếp bong bóng

Mặc dù sắp xếp bong bóng và sắp xếp chèn có cùng độ phức tạp thời gian chạy Big O, nhưng trên thực tế, sắp xếp chèn hiệu quả hơn đáng kể so với sắp xếp bong bóng. Nếu bạn nhìn vào việc triển khai cả hai thuật toán, thì bạn có thể thấy cách sắp xếp chèn phải thực hiện ít phép so sánh hơn để sắp xếp danh sách

Định thời gian thực hiện sắp xếp chèn của bạn

Để chứng minh khẳng định rằng sắp xếp chèn hiệu quả hơn sắp xếp nổi, bạn có thể tính thời gian cho thuật toán sắp xếp chèn và so sánh nó với kết quả của sắp xếp nổi. Để thực hiện việc này, bạn chỉ cần thay thế cuộc gọi thành

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

Bạn có thể thực thi tập lệnh như trước

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

Lưu ý cách triển khai sắp xếp chèn mất khoảng

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

Phân tích điểm mạnh và điểm yếu của sắp xếp chèn

Cũng giống như sắp xếp bong bóng, thuật toán sắp xếp chèn rất dễ thực hiện. Mặc dù sắp xếp chèn là thuật toán O(n2), nhưng trong thực tế, nó cũng hiệu quả hơn nhiều so với các triển khai bậc hai khác như sắp xếp bong bóng

Có nhiều thuật toán mạnh hơn, bao gồm sắp xếp hợp nhất và Quicksort, nhưng các triển khai này là đệ quy và thường không đánh bại được sắp xếp chèn khi làm việc trên các danh sách nhỏ. Một số triển khai Quicksort thậm chí sử dụng sắp xếp chèn bên trong nếu danh sách đủ nhỏ để cung cấp triển khai tổng thể nhanh hơn. Timsort cũng sử dụng sắp xếp chèn bên trong để sắp xếp các phần nhỏ của mảng đầu vào

Điều đó nói rằng, sắp xếp chèn không thực tế đối với các mảng lớn, mở ra cơ hội cho các thuật toán có thể mở rộng theo những cách hiệu quả hơn

Triển khai sắp xếp hợp nhất trong Python

Việc triển khai thuật toán sắp xếp hợp nhất cần hai phần khác nhau

1. Một hàm đệ quy chia đôi đầu vào
2. Một hàm hợp nhất cả hai nửa, tạo ra một mảng được sắp xếp

Đây là mã để hợp nhất hai mảng khác nhau

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

• Dòng 4 và 9 kiểm tra xem một trong hai mảng có trống không. Nếu một trong số chúng đúng, thì không có gì để hợp nhất, vì vậy hàm trả về mảng còn lại

• Dòng 17 bắt đầu một vòng lặp

  21ARRAY_LENGTH = 10000
  22
  23if __name__ == "__main__":
  24    # Generate an array of `ARRAY_LENGTH` items consisting
  25    # of random integer values between 0 and 999
  26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
  27
  28    # Call the function using the name of the sorting algorithm
  29    # and the array you just created
  30    run_sorting_algorithm(algorithm="sorted", array=array)
  

  49 kết thúc bất cứ khi nào kết quả chứa tất cả các phần tử từ cả hai mảng được cung cấp. Mục tiêu là xem xét cả hai mảng và kết hợp các phần tử của chúng để tạo ra một danh sách được sắp xếp

• Dòng 21 so sánh các phần tử ở đầu của cả hai mảng, chọn giá trị nhỏ hơn và nối nó vào cuối mảng kết quả

• Dòng 31 và 35 nối bất kỳ mục nào còn lại vào kết quả nếu tất cả các phần tử từ một trong hai mảng đã được sử dụng

Với chức năng trên, phần còn thiếu duy nhất là một hàm chia đệ quy mảng đầu vào thành một nửa và sử dụng

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

Đây là một bản tóm tắt nhanh chóng của mã

• Dòng 44 đóng vai trò là điều kiện dừng cho đệ quy. Nếu mảng đầu vào chứa ít hơn hai phần tử thì hàm trả về mảng. Lưu ý rằng điều kiện này có thể được kích hoạt bằng cách nhận một mục hoặc một mảng trống. Trong cả hai trường hợp, không còn gì để sắp xếp, vì vậy hàm sẽ trả về

• Dòng 47 tính điểm giữa của mảng

• Dòng 52 gọi

   1from random import randint
   2from timeit import repeat
   3
   4def run_sorting_algorithm(algorithm, array):
   5    # Set up the context and prepare the call to the specified
   6    # algorithm using the supplied array. Only import the
   7    # algorithm function if it's not the built-in `sorted()`.
   8    setup_code = f"from __main__ import {algorithm}" \
   9        if algorithm != "sorted" else ""
  10
  11    stmt = f"{algorithm}({array})"
  12
  13    # Execute the code ten different times and return the time
  14    # in seconds that each execution took
  15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
  16
  17    # Finally, display the name of the algorithm and the
  18    # minimum time it took to run
  19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
  

  01, chuyển cả hai nửa đã sắp xếp dưới dạng mảng

Lưu ý cách hàm này gọi chính nó theo cách đệ quy, chia đôi mảng mỗi lần. Mỗi lần lặp xử lý một mảng ngày càng thu hẹp cho đến khi còn lại ít hơn hai phần tử, nghĩa là không còn gì để sắp xếp. Tại thời điểm này,

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm(algorithm, array):
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted()`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}({array})"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

Hãy xem phần trình bày về các bước mà sắp xếp hợp nhất sẽ thực hiện để sắp xếp mảng

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm(algorithm="sorted", array=array)

Hình sử dụng các mũi tên màu vàng để biểu thị việc chia đôi mảng ở mỗi cấp độ đệ quy. Các mũi tên màu xanh lá cây đại diện cho việc hợp nhất từng mảng con lại với nhau. Các bước có thể được tóm tắt như sau

1. Cuộc gọi đầu tiên tới

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   07 với

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   71 định nghĩa

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   09 là

   21ARRAY_LENGTH = 10000
   22
   23if __name__ == "__main__":
   24    # Generate an array of `ARRAY_LENGTH` items consisting
   25    # of random integer values between 0 and 999
   26    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
   27
   28    # Call the function using the name of the sorting algorithm
   29    # and the array you just created
   30    run_sorting_algorithm(algorithm="sorted", array=array)
   

   74.

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   09 được sử dụng để chia đôi mảng đầu vào thành

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   12 và

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   13, tạo ra lần lượt là

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   14 và

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   15.

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   07 sau đó được gọi đệ quy cho mỗi nửa để sắp xếp chúng một cách riêng biệt

2. Cuộc gọi tới

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   07 với

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   14 tạo ra

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   64 và

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   20. Quá trình lặp lại cho mỗi nửa này

3. Cuộc gọi đến

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   07 với

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   64 trả về

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   64 vì đó là phần tử duy nhất. Điều tương tự cũng xảy ra với cuộc gọi tới

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   07 với

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   20

4. Tại thời điểm này, hàm bắt đầu hợp nhất các mảng con lại với nhau bằng cách sử dụng

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   01, bắt đầu với

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   64 và

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   20 làm mảng đầu vào, tạo ra kết quả là

   $ python sorting.py
   Algorithm: sorted. Minimum execution time: 0.010945824000000007
   

   31

5. Ở phía bên kia,

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   15 được chia nhỏ và hợp nhất theo cách đệ quy bằng cách sử dụng quy trình tương tự, tạo ra kết quả là

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   31

6. Ở bước cuối cùng,

   $ python sorting.py
   Algorithm: sorted. Minimum execution time: 0.010945824000000007
   

   31 và

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   31 được hợp nhất lại với nhau bằng

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   01, tạo ra kết quả cuối cùng.

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   35

Đo lường độ phức tạp Big O của Sắp xếp hợp nhất

Để phân tích mức độ phức tạp của sắp xếp hợp nhất, bạn có thể xem xét riêng hai bước của nó

1.  1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   01 có thời gian chạy tuyến tính. Nó nhận được hai mảng có độ dài kết hợp nhiều nhất là n (độ dài của mảng đầu vào ban đầu) và nó kết hợp cả hai mảng bằng cách xem xét từng phần tử nhiều nhất một lần. Điều này dẫn đến độ phức tạp thời gian chạy là O(n)

2. Bước thứ hai phân tách mảng đầu vào theo cách đệ quy và gọi

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   01 cho mỗi nửa. Vì mảng được chia đôi cho đến khi còn lại một phần tử nên tổng số thao tác chia đôi được thực hiện bởi hàm này là log2n. Vì

    1from random import randint
    2from timeit import repeat
    3
    4def run_sorting_algorithm(algorithm, array):
    5    # Set up the context and prepare the call to the specified
    6    # algorithm using the supplied array. Only import the
    7    # algorithm function if it's not the built-in `sorted()`.
    8    setup_code = f"from __main__ import {algorithm}" \
    9        if algorithm != "sorted" else ""
   10
   11    stmt = f"{algorithm}({array})"
   12
   13    # Execute the code ten different times and return the time
   14    # in seconds that each execution took
   15    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
   16
   17    # Finally, display the name of the algorithm and the
   18    # minimum time it took to run
   19    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")
   

   01 được gọi cho mỗi nửa, nên chúng ta có tổng thời gian chạy là O(n log2n)