Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Sắp xếp một mảng chuỗi theo thứ tự từ điển sử dụng thuật toán radix sort trong C
Thuật toán radix sort là một thuật toán sắp xếp không so sánh được sử dụng để sắp xếp các phần tử của một mảng. Trong trường hợp này, chúng ta sẽ áp dụng radix sort để sắp xếp một mảng các chuỗi theo thứ tự từ điển, tức là theo thứ tự alphabet. Trong bài viết này, mình sẽ tìm hiểu cách thực hiện điều này trong ngôn ngữ lập trình C.
Bài tập sắp xếp một mảng chuỗi theo thứ tự từ điển sử dụng thuật toán radix sort trong C
Cách giải quyết:
Thuật toán radix sort hoạt động bằng cách phân phối các phần tử của mảng vào các "bin" dựa trên giá trị của các chữ số từ hàng đơn vị đến hàng cao nhất. Dưới đây là một phần mã minh họa:
Dưới đây là một ví dụ về cách cài đặt thuật toán radix sort để sắp xếp một mảng chuỗi theo thứ tự từ điển trong ngôn ngữ lập trình C:
Bài viết này được đăng tại [free tuts .net]
#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 100
void countingSort(char arr[], int n, int exp) {
char output[n];
int count[256] = {0};
for (int i = 0; i < n; i++)
count[(int)arr[i] / exp % 256]++;
for (int i = 1; i < 256; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(int)arr[i] / exp % 256] - 1] = arr[i];
count[(int)arr[i] / exp % 256]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(char arr[], int n) {
int max_length = strlen(arr);
for (int exp = 1; max_length / exp > 0; exp *= 256)
countingSort(arr, n, exp);
}
// Hàm in ra màn hình freetuts.net
int main() {
int n;
printf("Nhập số lượng chuỗi trong mảng từ màn hình freetuts.net: ");
scanf("%d", &n);
char arr[n][MAX_LENGTH];
printf("Nhập các chuỗi của mảng từ màn hình freetuts.net:\n");
for (int i = 0; i < n; i++)
scanf("%s", arr[i]);
radixSort((char *)arr, n);
printf("Mảng sau khi sắp xếp là:\n");
for (int i = 0; i < n; i++)
printf("%s\n", arr[i]);
return 0;
}
Giải thích code:
- Trong hàm
countingSort(), mình sử dụng counting sort để sắp xếp các chuỗi theo chữ số từ hàng đơn vị đến hàng cao nhất. - Trong hàm
radixSort(), mình sử dụng radix sort để áp dụng counting sort cho mỗi chữ số trong các chuỗi. - Trong hàm
main(), mình nhập số lượng chuỗi và các chuỗi của mảng từ người dùng. Sau đó, chúng ta gọi hàm radixSort() để sắp xếp mảng và in ra kết quả.
Kết quả
Giả sử bạn nhập số lượng chuỗi là 5 và các chuỗi của mảng là "apple", "banana", "orange", "grape", "kiwi". Chương trình sẽ xuất ra:
Mảng sau khi sắp xếp là: apple banana grape kiwi orange
Trong bài viết này, mình đã tìm hiểu cách sử dụng thuật toán radix sort để sắp xếp một mảng các chuỗi theo thứ tự từ điển trong ngôn ngữ lập trình C. Điều này là một trong những kỹ thuật quan trọng để xử lý sắp xếp dữ liệu trong lập trình.
