Lập trình Python

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

Posted on by Đỗ Thành
lập trình code chuyên nghiệp
31
Th10
View: 58

Dưới đây là tổng hợp các thuật toán sắp xếp trong Python, bao gồm cả các hàm sắp xếp có sẵn trong Python.

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán sắp xếp đơn giản nhất. Thuật toán này được đặt tên là “nổi bọt” bởi vì các phần tử lớn sẽ “nổi lên” đến cuối danh sách trong quá trình sắp xếp.

Các bước thực hiện:

  1. Duyệt qua danh sách từ đầu đến cuối.
  2. So sánh hai phần tử liên tiếp. Nếu phần tử sau lớn hơn phần tử trước, hoán đổi chúng.
  3. Tiếp tục quá trình so sánh và hoán đổi cho đến khi không còn phần tử nào cần hoán đổi trong vòng lặp hiện tại.
  4. Lặp lại các bước trên cho đến khi toàn bộ danh sách đã được sắp xếp.

Code tham khảo:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # Duyệt qua danh sách từ đầu đến n-i-1 
        for j in range(0, n-i-1):
            # So sánh hai phần tử liền kề
            if arr[j] > arr[j+1]:
                # Hoán đổi phần tử nếu ptử sau lớn hơn ptử trước
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # Nếu không có phần tử nào cần hoán đổi trong lần duyệt này, danh sách đã sắp xếp
        if not swapped:
            break

# Ví dụ sử dụng:
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Danh sách đã sắp xếp:", arr)

Thuật toán sắp xếp nhanh (Quick Sort)

Thuật toán sắp xếp nhanh (QuickSort) là một trong những thuật toán sắp xếp hiệu quả và phổ biến. Nó dựa trên chiến lược “chia để trị,” tức là chia danh sách thành các phần nhỏ hơn, sắp xếp từng phần nhỏ này, và sau đó kết hợp chúng lại để tạo ra danh sách đã sắp xếp.

Quá trình của thuật toán sắp xếp nhanh bao gồm các bước sau:

  1. Chọn một phần tử làm pivot từ danh sách.
  2. Chia danh sách thành ba danh sách con: một danh sách chứa các phần tử nhỏ hơn pivot, một danh sách chứa các phần tử bằng pivot, và một danh sách chứa các phần tử lớn hơn pivot.
  3. Đệ quy sắp xếp danh sách nhỏ hơn và lớn hơn pivot.
  4. Kết hợp danh sách đã sắp xếp từ bước 3 với danh sách chứa các phần tử bằng pivot để tạo ra danh sách đã sắp xếp hoàn chỉnh.

Thuật toán sắp xếp nhanh thường có hiệu suất tốt với độ phức tạp trung bình là O(n log n), nhưng trong trường hợp xấu nhất có thể là O(n^2). Tuy nhiên, thường thì thuật toán này hoạt động tốt và được sử dụng rộng rãi trong thực tế. Code tham khảo:

def quick_sort(arr):
    # Kiểm tra nếu danh sách chỉ chứa một hoặc không có phần tử
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # Chọn phần tử giữa làm pivot
    left = [x for x in arr if x < pivot]  # Tạo danh sách các phần tử nhỏ hơn pivot
    middle = [x for x in arr if x == pivot]  # Tạo danh sách các phần tử bằng pivot
    right = [x for x in arr if x > pivot]  # Tạo danh sách các phần tử lớn hơn pivot
    
    # Đệ quy để sắp xếp danh sách left và right, sau đó kết hợp chúng lại với middle
    return quick_sort(left) + middle + quick_sort(right)

# Ví dụ sử dụng:
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("Danh sách đã sắp xếp:", sorted_arr)

Thuật toán sắp xếp chọn (Selection Sort)

Thuật toán sắp xếp chọn (Selection Sort) là một thuật toán sắp xếp đơn giản. Nó hoạt động bằng cách chọn phần tử nhỏ nhất từ danh sách và đưa nó vào đầu danh sách đã sắp xếp. Thuật toán này lặp lại quá trình này cho đến khi danh sách đã được sắp xếp hoàn toàn.

Quá trình của thuật toán sắp xếp chọn bao gồm các bước sau:

  1. Duyệt qua danh sách từ đầu đến cuối.
  2. Tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của danh sách.
  3. Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của danh sách chưa được sắp xếp.
  4. Lặp lại các bước 2 và 3 cho đến khi danh sách đã được sắp xếp hoàn toàn.

Thuật toán sắp xếp chọn có độ phức tạp thời gian luôn là O(n^2) trong mọi trường hợp, do đó nó không phải là thuật toán hiệu quả nhất cho danh sách lớn. Tuy nhiên, nó có cấu trúc đơn giản và dễ hiểu.

Code tham khảo:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i  # Giả sử phần tử đầu tiên trong danh sách chưa được sắp xếp là phần tử nhỏ nhất
        for j in range(i+1, n):
            # Tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của danh sách
            if arr[j] < arr[min_index]:
                min_index = j
        # Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của danh sách chưa được sắp xếp
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Ví dụ sử dụng:
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Danh sách đã sắp xếp:", arr)

Thuật toán sắp xếp chèn (Insertion Sort)

Thuật toán sắp xếp chèn (Insertion Sort) là một thuật toán sắp xếp đơn giản, nhưng hiệu quả đối với các danh sách nhỏ hoặc đã gần sắp xếp. Nó hoạt động bằng cách chia danh sách thành hai phần: một phần đã sắp xếp và một phần chưa sắp xếp. Thuật toán này duyệt qua từng phần tử trong phần chưa sắp xếp và chèn nó vào đúng vị trí trong phần đã sắp xếp.

Quá trình của thuật toán sắp xếp chèn bao gồm các bước sau:

  1. Bắt đầu từ phần tử thứ hai (vị trí 1) trong danh sách.
  2. Lưu trữ phần tử hiện tại cần chèn vào danh sách đã sắp xếp.
  3. Duyệt qua danh sách đã sắp xếp và dịch các phần tử lớn hơn key sang phải.
  4. Chèn key vào đúng vị trí trong danh sách đã sắp xếp.
  5. Lặp lại các bước 2 đến 4 cho đến khi danh sách đã được sắp xếp hoàn toàn.

Thuật toán sắp xếp chèn có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất, nhưng hiệu quả với danh sách đã gần sắp xếp và dễ dàng triển khai.

Code tham khảo:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]  # Lưu trữ phần tử hiện tại cần chèn vào danh sách đã sắp xếp
        j = i - 1
        # Duyệt qua danh sách đã sắp xếp và dịch các phần tử lớn hơn key sang phải
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Chèn key vào đúng vị trí trong danh sách đã sắp xếp

# Ví dụ sử dụng:
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("Danh sách đã sắp xếp:", arr)

Thuật toán sắp xếp hợp nhất (Merge Sort)

Thuật toán sắp xếp hợp nhất (Merge Sort) là một thuật toán sắp xếp dựa trên nguyên tắc “chia để trị”. Nó hoạt động bằng cách chia danh sách thành các nửa, sắp xếp từng nửa này, và sau đó kết hợp chúng lại để tạo ra danh sách đã sắp xếp. Merge Sort được biết đến với độ phức tạp thời gian ổn định và hiệu suất tốt cho danh sách lớn.

Quá trình của thuật toán sắp xếp hợp nhất bao gồm các bước sau:

  1. Chia danh sách thành hai nửa bằng cách tìm giữa danh sách.
  2. Đệ quy sắp xếp từng nửa riêng biệt.
  3. Kết hợp hai nửa đã sắp xếp lại với nhau bằng cách so sánh các phần tử của họ và xây dựng danh sách kết quả đã sắp xếp.

Thuật toán sắp xếp hợp nhất có độ phức tạp thời gian trung bình và xấu nhất đều là O(n log n), nên nó là một trong những thuật toán sắp xếp hiệu quả nhất. Code tham khảo:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # Chia danh sách thành hai nửa
    middle = len(arr) // 2
    left_half = arr[:middle]
    right_half = arr[middle:]
    
    # Đệ quy sắp xếp từng nửa
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    # Kết hợp hai nửa đã sắp xếp lại
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_index, right_index = 0, 0
    
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    
    # Nếu một trong hai nửa còn phần tử, thêm chúng vào danh sách kết quả
    result.extend(left[left_index:])
    result.extend(right[right_index:])
    
    return result

# Ví dụ sử dụng:
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("Danh sách đã sắp xếp:", sorted_arr)

Sử dụng hàm sắp xếp sort, sorted trong Python

Python cung cấp một số hàm sắp xếp có sẵn để giúp bạn sắp xếp danh sách hoặc dãy dữ liệu một cách dễ dàng và hiệu quả. Dưới đây là một số trong những hàm sắp xếp có sẵn trong Python:

sorted()

Hàm sorted() được sử dụng để sắp xếp một danh sách và trả về một danh sách mới đã sắp xếp, không làm thay đổi danh sách gốc.

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = sorted(arr)
print("Danh sách đã sắp xếp:", sorted_arr)

list.sort()

Phương thức sort() được gọi trên một danh sách và sắp xếp danh sách đó ngay tại chỗ, không trả về danh sách mới.

arr = [64, 34, 25, 12, 22, 11, 90]
arr.sort()
print("Danh sách đã sắp xếp:", arr)

sorted() với key function

Bạn có thể sử dụng tham số key để chỉ định một hàm tùy chỉnh để so sánh các phần tử.

arr = ["apple", "banana", "cherry", "date"]
sorted_arr = sorted(arr, key=lambda x: len(x))
print("Danh sách đã sắp xếp theo độ dài:", sorted_arr)

sorted() với tham số reverse

Bạn có thể sử dụng tham số reverse=True để sắp xếp danh sách theo thứ tự giảm dần.

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = sorted(arr, reverse=True)
print("Danh sách đã sắp xếp giảm dần:", sorted_arr)

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *