Thuật toán sắp xếp trong Python

Giới thiệu

Trong Python, có nhiều cách để sắp xếp một danh sách, và mỗi cách sắp xếp có độ phức tạp khác nhau. Để đánh giá độ phức tạp của các thuật toán sắp xếp trong Python, ta có thể sử dụng Big O notation. Big O notation là một cách để đánh giá tốc độ tăng của độ phức tạp thời gian hoặc không gian của một thuật toán khi đầu vào tăng lên.

Trong Python, có nhiều cách để sắp xếp một danh sách, và mỗi cách sắp xếp có độ phức tạp khác nhau. Để đánh giá độ phức tạp của các thuật toán sắp xếp trong Python, ta có thể sử dụng Big O notation. Big O notation là một cách để đánh giá tốc độ tăng của độ phức tạp thời gian hoặc không gian của một thuật toán khi đầu vào tăng lên.

Dưới đây là các thuật toán sắp xếp phổ biến trong Python và độ phức tạp tương ứng của chúng theo Big O notation:

1. Sắp xếp chọn (Selection Sort): O(n^2)
2. Sắp xếp chèn (Insertion Sort): O(n^2)
3. Sắp xếp nhanh (Quick Sort): O(nlogn) trung bình và O(n^2) trong trường hợp xấu nhất
4. Sắp xếp trộn (Merge Sort): O(nlogn)
5. Sắp xếp vun đống (Heap Sort): O(nlogn)
6. Sắp xếp giá trị (Bubble Sort): O(n^2)
7. Sắp xếp bọt (Cocktail Sort): O(n^2)

Có một số thuật toán sắp xếp khác nhưng các thuật toán này là những thuật toán phổ biến và được sử dụng nhiều nhất. Để chọn thuật toán sắp xếp phù hợp, chúng ta cần cân nhắc đến độ phức tạp thời gian và không gian của thuật toán, đầu vào của chương trình và mục đích sử dụng của chương trình.

Trong bài viết này chúng ta tập trung vào thuật toán Quicksort và các hàm sắp xếp có sẵn trong Python để thực hiện giải các bài toán về sắp xếp. Đây cũng là lựa chọn tốt nhất để có thể tối ưu hóa trong việc giải quyết các bài toán lập trình với ngôn ngữ lập trình Python.

Thuật toán Quicksort

Mô tả thuật toán

Thuật toán Quick sort là một thuật toán sắp xếp đệ quy dựa trên việc chia dãy ban đầu thành các phần tử nhỏ hơn và lớn hơn một phần tử chốt (pivot), sau đó sắp xếp các phần tử nhỏ hơn và lớn hơn pivot theo đúng thứ tự và tiếp tục áp dụng thuật toán đệ quy cho từng phần tử con.

Các bước thực hiện của thuật toán Quick sort:

1. Chọn một phần tử chốt (pivot) từ mảng đầu vào.
2. Chia mảng thành hai phần, một phần chứa các phần tử nhỏ hơn pivot và một phần chứa các phần tử lớn hơn pivot. Việc chia này có thể được thực hiện bằng cách sử dụng hai biến con trỏ (left và right) đối xứng nhau, lần lượt duyệt qua các phần tử của mảng và hoán đổi các phần tử để đưa chúng về phía tương ứng với phần chứa các phần tử nhỏ hơn hoặc lớn hơn pivot.
3. Áp dụng thuật toán Quick sort đệ quy cho hai phần tử con thu được ở bước 2. Điều này được thực hiện bằng cách lặp lại các bước 1 và 2 cho mỗi phần tử con.
4. Kết hợp các mảng con đã sắp xếp để tạo thành mảng đã được sắp xếp hoàn chỉnh.

Thuật toán Quick sort có thời gian chạy trung bình là O(nlogn) và được coi là một trong những thuật toán sắp xếp nhanh nhất. Tuy nhiên, trong trường hợp tệ nhất (nếu pivot là phần tử nhỏ nhất hoặc lớn nhất trong mảng), thời gian chạy của thuật toán Quick sort có thể là O(n^2), tương đương với thuật toán sắp xếp chọn.

Ví dụ về thuật toán

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quicksort(left) + [pivot] + quicksort(right)

Hàm quicksort được định nghĩa với đầu vào là một mảng arr. Nếu độ dài của mảng đó nhỏ hơn hoặc bằng 1, chúng ta trả về mảng đó luôn. Nếu không, chúng ta chọn một phần tử chốt làm pivot (ở đây là phần tử đầu tiên của mảng), tạo ra hai mảng con chứa các phần tử nhỏ hơn và lớn hơn pivot và sử dụng đệ quy để sắp xếp các mảng con đó. Cuối cùng, chúng ta kết hợp các mảng con đã sắp xếp với nhau và thêm pivot giữa chúng để tạo ra mảng đã được sắp xếp hoàn chỉnh.

Dưới đây là một ví dụ về sắp xếp một danh sách các số nguyên bằng Python, sử dụng thuật toán Quick sort:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quicksort(left) + [pivot] + quicksort(right)

# ví dụ
my_list = [5, 8, 1, 3, 7, 2, 4, 6]
print("Danh sách ban đầu: ", my_list)

my_list = quicksort(my_list)
print("Danh sách đã được sắp xếp: ", my_list)

Hàm sort() trong Python

Trong Python, hàm sort() được sử dụng để sắp xếp một danh sách các phần tử. Hàm này có thể được áp dụng cho các đối tượng có thể sắp xếp (sortable objects), chẳng hạn như danh sách (list), bộ (tuple) và các đối tượng tương tự.

Cú pháp của hàm sort() trong Python như sau:

list.sort(key=None, reverse=False)

Trong đó:

• list: danh sách các phần tử cần sắp xếp.
• key: là một hàm (function) được sử dụng để tạo ra một giá trị để so sánh và sắp xếp các phần tử. Giá trị mặc định của tham số này là None, trong trường hợp này sẽ sắp xếp các phần tử theo thứ tự tăng dần.
• reverse: là một cờ (flag) để xác định thứ tự sắp xếp là tăng dần (False) hay giảm dần (True). Giá trị mặc định của tham số này là False.

Ví dụ:

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
my_list.sort()
print(my_list)  # Output: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

my_list.sort(reverse=True)
print(my_list)  # Output: [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]

Chú ý rằng hàm sort() sẽ thay đổi danh sách ban đầu, nếu bạn không muốn thay đổi danh sách ban đầu, bạn có thể sử dụng hàm sorted() để tạo ra một danh sách mới đã được sắp xếp.

Hàm sorted() trong Python

Trong Python, hàm sorted() được sử dụng để sắp xếp một đối tượng có thể lặp lại (iterable) và trả về một danh sách mới chứa các phần tử đã được sắp xếp. Hàm này có thể được áp dụng cho các đối tượng có thể lặp lại như danh sách (list), bộ (tuple), và các đối tượng tương tự.

Cú pháp của hàm sorted() trong Python như sau:

sorted(iterable, key=None, reverse=False)

Trong đó:

• iterable: đối tượng cần sắp xếp.
• key: là một hàm (function) được sử dụng để tạo ra một giá trị để so sánh và sắp xếp các phần tử. Giá trị mặc định của tham số này là None, trong trường hợp này sẽ sắp xếp các phần tử theo thứ tự tăng dần.
• reverse: là một cờ (flag) để xác định thứ tự sắp xếp là tăng dần (False) hay giảm dần (True). Giá trị mặc định của tham số này là False.

Ví dụ:

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_list = sorted(my_list)
print(sorted_list)  # Output: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

sorted_list_desc = sorted(my_list, reverse=True)
print(sorted_list_desc)  # Output: [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]

Chú ý rằng hàm sorted() sẽ không thay đổi đối tượng ban đầu mà sẽ tạo ra một danh sách mới chứa các phần tử đã được sắp xếp.

Đánh giá độ phức tạp của các thuật toán

Độ phức tạp thời gian của thuật toán Quicksort trong trường hợp tốt nhất và trung bình là O(nlogn), và trong trường hợp xấu nhất là O(n^2). Tuy nhiên, với phân hoạch ngẫu nhiên và xử lý cẩn thận, trường hợp xấu nhất hiếm khi xảy ra trong thực tế.

Trong khi đó, các hàm sắp xếp có sẵn trong Python bao gồm hàm sort và hàm sorted, được viết bằng C và tối ưu hóa cho tốc độ, có độ phức tạp trung bình là O(nlogn). Nhờ tính tối ưu và được xử lý trực tiếp bằng ngôn ngữ thấp hơn, các hàm này sẽ hiệu quả hơn Quicksort trong nhiều trường hợp. Tuy nhiên, độ phức tạp thực tế của các hàm sắp xếp có thể khác nhau tùy thuộc vào tình huống cụ thể.

Khi cần sắp xếp các danh sách có kích thước lớn, các hàm sắp xếp có sẵn trong Python có thể nhanh hơn Quicksort. Tuy nhiên, khi cần sắp xếp các danh sách nhỏ hoặc danh sách có tính chất đặc biệt, Quicksort có thể là sự lựa chọn tốt hơn. Vì vậy, lựa chọn giữa Quicksort và các hàm sắp xếp có sẵn trong Python tùy thuộc vào tình huống cụ thể./.