#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void append(Node** head_ref, int new_data) {
Node* new_node = (Node*)malloc(sizeof(Node));
Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int getMax(Node* head) {
int max = head->data;
while (head != NULL) {
if (head->data > max) {
max = head->data;
}
head = head->next;
}
return max;
}
void countingSort(Node** head_ref, int exp) {
Node* output = NULL; // Lista de salida
int count[10] = {0};
Node* current = *head_ref;
// Contar ocurrencias
while (current != NULL) {
count[(current->data / exp) % 10]++;
current = current->next;
}
// Cambiar count para que contenga la posición real de este dígito en output
for(int i = 1; i < 10; i++) {
count += count[i - 1];
}
// Construir la lista de salida
current = *head_ref;
while (current != NULL) {
int index = (current->data / exp) % 10;
append(&output, current->data);
count[index]--;
current = current->next;
}
// Copiar la lista de salida a head_ref
*head_ref = output;
}
void radixSort(Node** head_ref) {
int max = getMax(*head_ref);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(head_ref, exp);
printf("Lista después de ordenar por el dígito en la posición %d: ", exp);
printList(*head_ref);
}
}
int main() {
Node* head = NULL;
append(&head, 170);
append(&head, 45);
append(&head, 75);
append(&head, 90);
append(&head, 802);
append(&head, 24);
append(&head, 2);
append(&head, 66);
printf("Lista original: ");
printList(head);
radixSort(&head);
printf("Lista ordenada: ");
printList(head);
return 0;
}