Trong hướng dẫn này, bạn sẽ tìm hiểu cách sắp xếp cơ số hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp cơ số trong C, C ++, Java và Python.
Sắp xếp theo cơ số là một kỹ thuật sắp xếp sắp xếp các phần tử bằng cách nhóm các chữ số riêng lẻ của cùng một giá trị vị trí . Sau đó, sắp xếp các phần tử theo thứ tự tăng / giảm của chúng.
Giả sử, chúng ta có một mảng gồm 8 phần tử. Đầu tiên, chúng tôi sẽ sắp xếp các phần tử dựa trên giá trị của vị trí đơn vị. Sau đó, chúng tôi sẽ sắp xếp các phần tử dựa trên giá trị của vị trí thứ mười. Quá trình này tiếp tục cho đến nơi quan trọng cuối cùng.
Cho mảng ban đầu là (121, 432, 564, 23, 1, 45, 788). Nó được sắp xếp theo cơ số sắp xếp như trong hình bên dưới.
Hoạt động của Radix Sort
Vui lòng xem qua sắp xếp đếm trước khi đọc bài viết này vì sắp xếp đếm được sử dụng như một sắp xếp trung gian trong sắp xếp cơ số.
Radix Sort hoạt động như thế nào?
- Tìm phần tử lớn nhất trong mảng, tức là max. Gọi
Xlà số chữ số trongmax.Xđược tính toán bởi vì chúng ta phải đi qua tất cả các vị trí quan trọng của tất cả các yếu tố.
Trong mảng này(121, 432, 564, 23, 1, 45, 788), chúng ta có số lớn nhất 788. Nó có 3 chữ số. Do đó, vòng lặp nên lên đến hàng trăm (3 lần). - Bây giờ, hãy lần lượt đi qua từng địa điểm quan trọng.
Sử dụng bất kỳ kỹ thuật sắp xếp ổn định nào để sắp xếp các chữ số ở mỗi vị trí quan trọng. Chúng tôi đã sử dụng sắp xếp đếm cho việc này.
Sắp xếp các phần tử dựa trên các chữ số hàng đơn vị (X=0).
Sử dụng sắp xếp đếm để sắp xếp các phần tử dựa trên vị trí đơn vị - Bây giờ, hãy sắp xếp các phần tử dựa trên các chữ số ở hàng chục.
Sắp xếp các phần tử dựa trên hàng chục - Cuối cùng, sắp xếp các phần tử dựa trên các chữ số ở vị trí hàng trăm.
Sắp xếp các phần tử dựa trên hàng trăm vị trí
Thuật toán sắp xếp theo Radix
radixSort (mảng) d <- số chữ số tối đa trong phần tử lớn nhất tạo d nhóm có kích thước 0-9 cho i <- 0 để d sắp xếp các phần tử theo chữ số thứ i bằng cách sử dụng countSort countSort (array, d) max <- find phần tử lớn nhất trong số các phần tử ở vị trí thứ d khởi tạo mảng đếm với tất cả các số không cho j <- 0 để kích thước tìm tổng số của mỗi chữ số duy nhất ở vị trí thứ d của phần tử và lưu trữ số đếm ở chỉ số thứ j trong mảng đếm cho i <- 1 để tìm tối đa tổng tích lũy và lưu trữ nó trong chính mảng đếm cho j <- kích thước xuống 1 khôi phục các phần tử vào mảng giảm số lượng của mỗi phần tử được khôi phục 1
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)
// Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
// Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
Phức tạp
Vì sắp xếp cơ số là một thuật toán không so sánh, nó có lợi thế hơn các thuật toán sắp xếp so sánh.
Đối với sắp xếp cơ số sử dụng sắp xếp đếm như một sắp xếp ổn định trung gian, độ phức tạp về thời gian là O(d(n+k)).
Đây, dlà chu kỳ số và O(n+k)là độ phức tạp về thời gian của sắp xếp đếm.
Do đó, sắp xếp cơ số có độ phức tạp theo thời gian tuyến tính tốt hơn so với O(nlog n)các thuật toán sắp xếp so sánh.
Nếu chúng ta lấy các số có chữ số rất lớn hoặc số các cơ số khác như số 32-bit và 64-bit thì nó có thể thực hiện trong thời gian tuyến tính tuy nhiên sắp xếp trung gian chiếm không gian lớn.
Điều này làm cho không gian sắp xếp cơ số không hiệu quả. Đây là lý do tại sao loại này không được sử dụng trong thư viện phần mềm.
Ứng dụng sắp xếp Radix
Sắp xếp theo cơ số được triển khai trong
- Thuật toán DC3 (Kärkkäinen-Sanders-Burkhardt) trong khi tạo mảng hậu tố.
- những nơi có số lượng trong phạm vi lớn.
