Nguyên lý các thuật toán sắp xếp phổ biến

1. Sắp xếp nổi bọt (Bubble Sort)

Thuật toán này hoạt động bằng cách liên tục so sánh hai phần tử kề nhau. Nếu phần tử đứng trước lớn hơn phần tử đứng sau, chúng ta tiến hành hoán đổi vị trí hai phần tử này. Quá trình lặp lại cho đến khi toàn bộ mảng được duyệt qua mà không cần thực hiện bất kỳ phép hoán đổi nào. Trong mỗi vòng lặp, phần tử lớn nhất sẽ "nổi" lên vị trí cuối cùng của dãy hiện hành.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

2. Sắp xếp chọn (Selection Sort)

Phương pháp này chia mảng thành hai phần: đã sắp xếp và chưa sắp xếp. Tại mỗi bước, nó tìm phần tử nhỏ nhất trong phần chưa sắp xếp và hoán đổi vị trí với phần tử đầu tiên của phần chưa sắp xếp, từ đó mở rộng ranh giới của phần đã sắp xếp.

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

3. Sắp xếp chèn (Insertion Sort)

Thuật toán này xây dựng mảng kết quả từng phần tử một. Nó lấy từng phần tử từ mảng gốc và chèn vào đúng vị trí của nó trong mảng đã sắp xếp. Quá trình tương tự như cách bạn sắp xếp lại một bộ bài tẩy trên tay.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

4. Sắp xếp Shell (Shell Sort)

Là một cải tiến của sắp xếp chèn, thuật toán này cho phép hoán đổi các phần tử nằm xa nhau. Ban đầu, nó chọn một khoảng cách (gap) lớn để chia mảng thành các nhóm con và sắp xếp chúng. Sau đó, khoảng cách này dần được thu hẹp lại. Khi khoảng cách bằng 1, thuật toán trở thành sắp xếp chèn thông thường nhưng trên một mảng đã gần như sắp xếp, giúp tối ưu thời gian.

def shell_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

5. Sắp xếp trộn (Merge Sort)

Sử dụng phương pháp chia để trị. Thuật toán chia mảng thành hai nửa, đệ quy gọi hàm sắp xếp cho từng nửa, sau đó gộp hai nửa đã được sắp xếp lại. Việc gộp được thực hiện bằng cách so sánh phần tử đầu tiên của mỗi nửa và chọn phần tử nhỏ hơn đưa vào mảng kết quả.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

6. Sắp xếp nhanh (Quick Sort)

Thuật toán chọn một phần tử làm điểm chuẩn (pivot). Mảng được phân vùng sao cho tất cả phần tử nhỏ hơn pivot nằm bên trái, lớn hơn nằm bên phải. Sau đó, nó đệ quy thực hiện tương tự cho các phân vùng bên trái và bên phải.

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

7. Sắp xếp vun đống (Heap Sort)

Dựa trên cấu trúc dữ liệu cây nhị phân hoàn chỉnh (Heap). Đầu tiên, mảng được biến đổi thành một max heap (nút cha luôn lớn hơn nút con). Sau đó, phần tử lớn nhất (nằm ở gốc) được đưa về cuối mảng, giảm kích thước heap và lặp lại quá trình vun đống (heapify) cho phần còn lại.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

8. Sắp xếp đếm (Counting Sort)

Thuật toán này không dựa trên so sánh. Nó áp dụng cho các kiểu dữ liệu nguyên thủy có phạm vi giá trị hạn chế. Bằng cách đếm số lần xuất hiện của từng phần tử, ta có thể xác định chính xác vị trí cuối cùng của chúng trong mảng kết quả.

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    index = 0
    for i in range(len(count)):
        while count[i] > 0:
            arr[index] = i
            index += 1
            count[i] -= 1

9. Sắp xếp phân lô (Bucket Sort)

Chia dải đầu vào thành các khoảng (hoặc lô - bucket) bằng nhau. Các phần tử được phân bổ vào các lô này. Sau đó, từng lô được sắp xếp nội bộ (thường dùng sắp xếp chèn), và cuối cùng nối tất cả các lô lại theo thứ tự để tạo thành mảng hoàn chỉnh.

10. Sắp xếp cơ số (Radix Sort)

Thuật toán xử lý các số nguyên từng chữ số một. Nó bắt đầu từ chữ số cuối cùng (LSD) hoặc đầu tiên (MSD), sắp xếp các phần tử dựa trên giá trị của chữ số đó. Quá trình lặp lại cho đến khi tất cả các chữ số được duyệt qua. Các thuật toán phụ như sắp xếp đếm thường được dùng làm công cụ trung gian.

So sánh các thuật toán sắp xếp không dựa trên so sánh

Cả ba thuật toán Sắp xếp phân lô, Sắp xếp đếm và Sắp xếp cơ số đều tận dụng khái niệm "bucket" (lô chứa), nhưng cách thức sử dụng khác biệt:

• Radix Sort: Phân bổ phần tử vào các lô dựa trên giá trị của từng chữ số.
• Counting Sort: Mỗi lô chỉ lưu trữ số lượng phần tử có một giá trị duy nhất.
• Bucket Sort: Mỗi lô lưu trữ một dải giá trị liên tiếp.

Tổng kết độ phức tạp

Dưới đây là đánh giá tổng quát về độ phức tạp thời gian, không gian và tính ổn định của các thuật toán:

• Sắp xếp nổi bọt: Độ phức tạp thời gian trung bình O(n^2), ổn định, không gian O(1).
• Sắp xếp chọn: O(n^2), không ổn định, không gian O(1).
• Sắp xếp chèn: O(n^2), ổn định, không gian O(1).
• Sắp xếp Shell: O(n log n) đến O(n^2), không ổn định, không gian O(1).
• Sắp xếp trộn: O(n log n), ổn định, không gian O(n).
• Sắp xếp nhanh: O(n log n) trung bình, O(n^2) xấu nhất, không ổn định, không gian O(log n).
• Sắp xếp vun đống: O(n log n), không ổn định, không gian O(1).
• Counting/Bucket/Radix Sort: Có thể đạt O(n) với điều kiện đầu vào phù hợp, tính ổn định tùy biến thể cài đặt, không gian O(k) hoặc O(n+k).