Sắp xếp cơ số DSA

Sắp xếp cơ số

Thuật toán Radix Sort sắp xếp một mảng theo các chữ số riêng lẻ, bắt đầu bằng chữ số có nghĩa thấp nhất (số ngoài cùng bên phải).

Cơ số (hoặc cơ số) là số chữ số duy nhất trong một hệ thống số. Trong hệ thập phân chúng ta thường sử dụng, có 10 chữ số khác nhau từ 0 đến 9.

Radix Sort sử dụng cơ số để các giá trị thập phân được đưa vào 10 nhóm (hoặc vùng chứa) khác nhau tương ứng với chữ số được lấy nét, sau đó đặt lại vào mảng trước khi chuyển sang chữ số tiếp theo.

Sắp xếp cơ số là một thuật toán không so sánh, chỉ hoạt động với các số nguyên không âm.

Thuật toán Radix Sort có thể được mô tả như sau:

Sắp xếp ổn định

Radix Sort phải sắp xếp các phần tử một cách ổn định để kết quả được sắp xếp chính xác.

Thuật toán sắp xếp ổn định là thuật toán giữ thứ tự các phần tử có cùng giá trị trước và sau khi sắp xếp. Giả sử chúng ta có hai phần tử "K" và "L", trong đó "K" đứng trước "L" và cả hai đều có giá trị "3". Thuật toán sắp xếp được coi là ổn định nếu phần tử "K" vẫn đứng trước "L" sau khi mảng được sắp xếp.

Sẽ không có ý nghĩa gì khi nói về các thuật toán sắp xếp ổn định cho các thuật toán trước đây mà chúng ta đã xem xét riêng lẻ, bởi vì kết quả sẽ giống nhau cho dù chúng có ổn định hay không. Nhưng điều quan trọng đối với Radix Sort là việc sắp xếp được thực hiện một cách ổn định vì các phần tử được sắp xếp chỉ theo một chữ số mỗi lần.

Vì vậy, sau khi sắp xếp các phần tử ở chữ số có nghĩa nhỏ nhất và chuyển sang chữ số tiếp theo, điều quan trọng là không được phá hủy công việc sắp xếp đã được thực hiện ở vị trí chữ số trước đó và đó là lý do tại sao chúng ta cần quan tâm đến Radix Sort. việc sắp xếp theo từng vị trí chữ số một cách ổn định.

Trong mô phỏng bên dưới, nó cho thấy cách thực hiện việc sắp xếp cơ bản thành các nhóm. Và để hiểu rõ hơn về cách sắp xếp ổn định, bạn cũng có thể chọn cách sắp xếp không ổn định, điều đó sẽ dẫn đến kết quả không chính xác. Việc sắp xếp trở nên không ổn định bằng cách đơn giản đặt các phần tử vào các nhóm từ cuối mảng thay vì từ đầu mảng.

Chạy qua thủ công

Chúng ta hãy thử thực hiện việc sắp xếp theo cách thủ công, để hiểu rõ hơn về cách hoạt động của Radix Sort trước khi thực sự triển khai nó bằng ngôn ngữ lập trình.

Bước 1: Chúng ta bắt đầu với một mảng chưa được sắp xếp và một mảng trống để khớp các giá trị có hệ số tương ứng từ 0 đến 9.

Bước 2: Chúng ta bắt đầu sắp xếp bằng cách tập trung vào chữ số có nghĩa nhỏ nhất.

Bước 3: Bây giờ chúng ta di chuyển các phần tử vào đúng vị trí trong mảng cơ số theo chữ số cần lấy nét. Các phần tử được lấy từ đầu myArray và được đẩy vào đúng vị trí trong cơ số.

Bước 4: Chúng ta di chuyển các phần tử trở lại mảng ban đầu và việc sắp xếp hiện đã được thực hiện cho chữ số có nghĩa nhỏ nhất. Các phần tử được lấy từ cơ số cuối cùng và đưa vào phần đầu của myArray.

Bước 5: Chúng ta chuyển tiêu điểm sang chữ số tiếp theo. Lưu ý rằng các giá trị 45 và 25 vẫn có cùng thứ tự so với nhau như ban đầu vì chúng tôi sắp xếp theo cách ổn định.

Bước 6: Chúng ta di chuyển các phần tử vào mảng cơ số theo chữ số tập trung.

Bước 7: Chúng ta di chuyển các phần tử trở lại phần đầu của myArray, từ phía sau của radixArray.

Việc phân loại đã hoàn tất!

Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:

Chạy qua thủ công: Chuyện gì đã xảy ra?

Chúng ta thấy rằng các giá trị được di chuyển khỏi mảng và được đặt trong mảng cơ số theo cơ số hiện tại đang được lấy nét. Và sau đó các giá trị được chuyển trở lại mảng mà chúng ta muốn sắp xếp.

Việc di chuyển các giá trị từ mảng mà chúng ta muốn sắp xếp và quay lại phải được thực hiện nhiều lần bằng số chữ số tối đa trong một giá trị. Vì vậy, ví dụ nếu 437 là số cao nhất trong mảng cần được sắp xếp, chúng ta biết rằng chúng ta phải sắp xếp ba lần, một lần cho mỗi chữ số.

Chúng ta cũng thấy rằng mảng cơ số cần phải có hai chiều để có nhiều hơn một giá trị trên một cơ số hoặc chỉ mục cụ thể.

Và, như đã đề cập trước đó, chúng ta phải di chuyển các giá trị giữa hai mảng theo cách giữ thứ tự của các giá trị có cùng cơ số trong tiêu điểm, để việc sắp xếp được ổn định.

Triển khai sắp xếp cơ số

Để thực hiện thuật toán Radix Sort chúng ta cần:

1. Một mảng có các số nguyên không âm cần được sắp xếp.
2. Mảng hai chiều có chỉ số từ 0 đến 9 để giữ các giá trị có cơ số hiện tại đang được lấy nét.
3. Vòng lặp lấy các giá trị từ mảng chưa được sắp xếp và đặt chúng vào đúng vị trí trong mảng cơ số hai chiều.
4. Một vòng lặp đưa các giá trị trở lại mảng ban đầu từ mảng cơ số.
5. Một vòng lặp bên ngoài chạy với số lần bằng số chữ số có giá trị cao nhất.

Mã kết quả trông như thế này:

 myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(myArray)
exp = 1

while maxVal // exp > 0:

    while len(myArray) > 0:
        val = myArray.pop()
        radixIndex = (val // exp) % 10
        radixArray[radixIndex].append(val)

    for bucket in radixArray:
        while len(bucket) > 0:
            val = bucket.pop()
            myArray.append(val)

    exp *= 10

print("Sorted array:", myArray)

Ở dòng 7 , chúng ta sử dụng phép chia sàn ("//") để chia giá trị lớn nhất 802 cho 1 ở lần đầu vòng lặp while chạy, lần sau chia cho 10 và lần cuối chia cho 100. Khi sử dụng phép chia sàn "//", bất kỳ số nào ngoài dấu thập phân đều bị bỏ qua và một số nguyên được trả về.

Trên dòng 11 , vị trí đặt giá trị trong cơ số được quyết định dựa trên cơ số hoặc chữ số tiêu điểm của nó. Ví dụ: lần thứ hai vòng lặp while bên ngoài chạy exp sẽ là 10. Giá trị 170 chia cho 10 sẽ là 17. Thao tác "%10" chia cho 10 và trả về số còn lại. Trong trường hợp này, 17 được chia cho 10 một lần và còn lại 7. Vì vậy, giá trị 170 được đặt ở chỉ mục 7 trong cơ số.

Sắp xếp cơ số bằng các thuật toán sắp xếp khác

Radix Sort thực sự có thể được triển khai cùng với bất kỳ thuật toán sắp xếp nào khác miễn là nó ổn định. Điều này có nghĩa là khi sắp xếp theo một chữ số cụ thể, bất kỳ thuật toán sắp xếp ổn định nào cũng sẽ hoạt động, chẳng hạn như sắp xếp đếm hoặc sắp xếp bong bóng.

Đây là cách triển khai Sắp xếp cơ số sử dụng Sắp xếp nổi bọt để sắp xếp theo từng chữ số:

 def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                
def radixSortWithBubbleSort(arr):
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        radixArray = [[],[],[],[],[],[],[],[],[],[]]
        
        for num in arr:
            radixIndex = (num // exp) % 10
            radixArray[radixIndex].append(num)
        
        for bucket in radixArray:
            bubbleSort(bucket)
        
        i = 0
        for bucket in radixArray:
            for num in bucket:
                arr[i] = num
                i += 1
        
        exp *= 10

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixSortWithBubbleSort(myArray)
print("Sorted array:", myArray)

Độ phức tạp thời gian sắp xếp cơ số

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp của thời gian Sắp xếp Cơ số, hãy truy cập trang này .

Độ phức tạp về thời gian của Radix Sort là:

\[ \underline{\underline{O(n \cdot k)}} \]

Điều này có nghĩa là Sắp xếp theo cơ số phụ thuộc cả vào các giá trị cần được sắp xếp \(n\) và số chữ số ở giá trị cao nhất \(k\).

Trường hợp tốt nhất cho Sắp xếp theo cơ số là nếu có nhiều giá trị cần sắp xếp nhưng các giá trị đó có ít chữ số. Ví dụ: nếu có hơn một triệu giá trị cần sắp xếp và giá trị cao nhất là 999, chỉ có ba chữ số. Trong trường hợp như vậy, độ phức tạp về thời gian \(O(n \cdot k)\) có thể được đơn giản hóa thành \(O(n)\).

Trường hợp xấu nhất đối với Sắp xếp theo cơ số sẽ là nếu có nhiều chữ số ở giá trị cao nhất bằng số giá trị cần sắp xếp. Đây có lẽ không phải là một tình huống phổ biến, nhưng độ phức tạp về thời gian sẽ là \(O(n^2)\) trong trường hợp này.

Trường hợp trung bình hoặc phổ biến nhất có lẽ là nếu số chữ số \(k\) giống như \(k(n)= \log n\). Nếu vậy, Sắp xếp Cơ số sẽ có độ phức tạp về thời gian \(O(n \cdot \log n )\). Một ví dụ về trường hợp như vậy là nếu có 1000000 giá trị cần sắp xếp và các giá trị có 6 chữ số.

Xem độ phức tạp về thời gian khác nhau có thể có đối với Sắp xếp Cơ số trong hình ảnh bên dưới.

Chạy các mô phỏng khác nhau của Sắp xếp cơ số để xem số lượng thao tác nằm giữa trường hợp xấu nhất \(O(n^2)\) (đường màu đỏ) và trường hợp tốt nhất \(O(n)\) (đường màu xanh lá cây).

Các thanh đại diện cho các giá trị khác nhau được điều chỉnh tỷ lệ cho vừa với cửa sổ để trông ổn. Điều này có nghĩa là các giá trị có 7 chữ số trông có vẻ lớn hơn 5 lần so với các giá trị có 2 chữ số, nhưng trên thực tế, các giá trị có 7 chữ số thực sự lớn hơn 5000 lần so với các giá trị có 2 chữ số!

Nếu chúng ta giữ cố định \(n\) và \(k\) thì các lựa chọn thay thế "Ngẫu nhiên", "Giảm dần" và "Tăng dần" trong mô phỏng ở trên sẽ dẫn đến cùng một số thao tác. Điều này là do điều tương tự xảy ra trong cả ba trường hợp.

Sắp xếp cơ số phải sử dụng một 
thuật toán sắp xếp.