使用队列进行基数排序 [英] Radix Sorting with using queue
问题描述
我想使用队列创建一个基数排序实现.
I've wanted to create a radix sort implementation using queues.
我不知道我的代码的哪一部分有问题，或者我应该阅读哪些资源.我的代码可能完全错误，但这是我没有任何帮助的实现(我还没有参加数据结构和算法课程).
I couldn't figure out which part of my code has problems or which resources should I read. My code may be totally wrong but this is my implementation without any help (I haven't taken a data structures & algorithms course yet).
我创建了一个函数，但它不起作用.在做研究时，我看到了一些代码示例，但对我来说它们似乎更复杂.
I created a function but it didn't work. While doing research, I saw some code samples but they seemed to be more complex for me.
首先我想找到所有整数的最低有效位然后将它们排序在下标匹配的队列元素中，then 排序后将所有队列复制到第 11 个队列元素的末尾.再次在第 11 个队列元素中进行排序，直到达到最高有效位.
Firstly I wanted to find the least significant digit of all integers Then sort them in queue element whose subscript matches, then after sort copy all queues to end of 11th queue element. Do this sort in 11th queue element again until reach most significant digit.
我能找到最低有效数字.并按此数字排序.但是，我无法分析其他数字.例如;我可以对 1, 2 , 4, 5, 3 进行排序，但是当需要对 2 个或更多数字进行排序时，它会失败...
I could find least significant digit. And sort according to this digit. But, I couldn't analyse other digits. For instance; I could sort 1, 2 , 4, 5, 3 but when time comes to sort 2 or more digits, it fails...
我希望我很清楚并简要解释了我的问题.
I hope, I was clear and explained my problem briefly.
// My function declaration
// Pre: arrInts holds the linked list of integers which are going to be sort.
// Post: queue will return result and its 11th element should hold sorted integers in
// that queue
queue_node_t * radixSort(const queue_node_t *arrInts, queue_t *queue[], int size){
queue_node_t *curNodep = arrInts; // Node to be checked
int i, curNum = curNodep->element.key;
if(curNodep == NULL){
// If there is no other node left then assign them into 11th queue.
for(i=0;i<=9;i++){
if(queue[i]->rearp!=NULL){
if(queue[10]->size == 0){
queue[10]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[10]->frontp = queue[10]->rearp;
} else {
queue[10]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[10]->rearp = queue[10]->rearp->restp;
}
queue[10]->rearp = queue[i]->rearp;
queue[10]->size += queue[i]->size;
}
}
queue[10]->rearp = radixSort(queue[10]->rearp, queue, size);
} else {
// I used switch statement to handle least significant digit
switch(curNum%10){
case 0:
if(queue[0]->size == 0){
queue[0]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[0]->frontp = queue[0]->rearp;
} else {
queue[0]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[0]->rearp = queue[0]->rearp->restp;
}
++(queue[0]->size);
queue[0]->rearp->element = curNodep->element;
queue[0]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 1:
if(queue[1]->size == 0){
queue[1]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[1]->frontp = queue[0]->rearp;
} else {
queue[1]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[1]->rearp = queue[1]->rearp->restp;
}
++(queue[1]->size);
queue[1]->rearp->element = curNodep->element;
queue[1]->rearp->restp = NULL;
// I tried to make recursion but I guess this is one the problems
radixSort(curNodep->restp, queue, size);
break;
case 2:
if(queue[2]->size == 0){
queue[2]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[2]->frontp = queue[2]->rearp;
} else {
queue[2]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[2]->rearp = queue[2]->rearp->restp;
}
++(queue[2]->size);
queue[2]->rearp->element = curNodep->element;
queue[2]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 3:
if(queue[3]->size == 0){
queue[3]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[3]->frontp = queue[3]->rearp;
} else {
queue[3]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[3]->rearp = queue[3]->rearp->restp;
}
++(queue[3]->size);
queue[3]->rearp->element = curNodep->element;
queue[3]->rearp->restp = NULL;
queue[10]->rearp = radixSort(curNodep->restp, queue, size);
break;
case 4:
if(queue[4]->size == 0){
queue[4]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[4]->frontp = queue[4]->rearp;
} else {
queue[4]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[4]->rearp = queue[4]->rearp->restp;
}
++(queue[4]->size);
queue[4]->rearp->element = curNodep->element;
queue[4]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 5:
if(queue[5]->size == 0){
queue[5]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[5]->frontp = queue[5]->rearp;
} else {
queue[5]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[5]->rearp = queue[5]->rearp->restp;
}
++(queue[5]->size);
queue[5]->rearp->element = curNodep->element;
queue[5]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 6:
if(queue[6]->size == 0){
queue[6]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[6]->frontp = queue[6]->rearp;
} else {
queue[6]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[6]->rearp = queue[6]->rearp->restp;
}
++(queue[6]->size);
queue[6]->rearp->element = curNodep->element;
queue[6]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 7:
if(queue[7]->size == 0){
queue[7]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[7]->frontp = queue[7]->rearp;
} else {
queue[7]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[7]->rearp = queue[7]->rearp->restp;
}
++(queue[7]->size);
queue[7]->rearp->element = curNodep->element;
queue[7]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 8:
if(queue[8]->size == 0){
queue[8]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[8]->frontp = queue[8]->rearp;
} else {
queue[8]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[8]->rearp = queue[8]->rearp->restp;
}
++(queue[8]->size);
queue[8]->rearp->element = curNodep->element;
queue[8]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
case 9:
if(queue[9]->size == 0){
queue[9]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[9]->frontp = queue[9]->rearp;
} else {
queue[9]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[9]->rearp = queue[9]->rearp->restp;
}
++(queue[9]->size);
queue[9]->rearp->element = curNodep->element;
queue[9]->rearp->restp = NULL;
radixSort(curNodep->restp, queue, size);
break;
}
}
return queue[10]->rearp;
}
编辑 1(取得一些进展)
我遵循了威廉莫里斯的建议.我不得不在 CodeReview 上问同样的问题，他给了我一些说明，让我的代码更清晰.
I followed suggestions from William Morris. I had to ask same question on CodeReview and he gave me some instructions to make my code clearer.
我把我的函数分成了函数，也不再使用递归了.
I divided my function into functions and also stopped using recursion.
首先，我创建了一个 add_to_q 函数，它将值添加到相关队列，它有助于摆脱代码重复.顺便说一下，James Khoury 的方法是最简单的方法，但它再次使用了递归.
Firstly, I created a add_to_q function which adds value to related queue and it helped to get rid of code duplication. By the way James Khoury's way is simplest one but it again uses recursion.
void add_to_q(queue_t *queue_arr[], int value, int pos) {
if(queue_arr[pos]->size == 0){
queue_arr[pos]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue_arr[pos]->frontp = queue_arr[pos]->rearp;
} else {
queue_arr[pos]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue_arr[pos]->rearp = queue_arr[pos]->rearp->restp;
}
queue_arr[pos]->rearp->element = value;
queue_arr[pos]->size++;
}
其次我创建了其他辅助函数.一个是 add_to_eleventh，它只是将所有队列元素添加到第 11 个队列的尾部.在我看来，它正在做问题想要的.
Secondly I created other helper functions. One is add_to_eleventh which simply adds all queue elements to the eleventh queue's rear. In my opinion, it is doing what question wants.
queue_t * add_to_eleventh(queue_t *queue[]) {
int i;
for(i=0;i<=9;i++){
while(queue[i]->frontp != NULL){
if(queue[10]->size == 0){
queue[10]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t));
queue[10]->frontp = queue[10]->rearp;
} else {
queue[10]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t));
queue[10]->rearp = queue[10]->rearp->restp;
}
if ( queue[i]->size != 0 ){
queue[10]->rearp->element = queue[i]->frontp->element;
printf("---%d***",queue[i]->frontp->element);
}
queue[10]->size+=1;
queue[i]->frontp = queue[i]->frontp->restp;
queue[10]->rearp->restp = NULL;
}
}
return queue[10];
}
第三，我的最后一个辅助函数是 back_to_ints.其目的是将第11个队列中的元素除以10，并以整数数组形式返回.
Thirdly, my last helper function is back_to_ints. Its purpose is take the elements in 11th queue and divide them by ten and return them in a integer array.
void back_to_ints(queue_t *arr[], int *new_arr) {
queue_node_t *cur_nodep;
cur_nodep = arr[10]->frontp;
int i = 0, digit;
while(cur_nodep != NULL){
cur_nodep->element/=10;
digit = cur_nodep->element / 10;
new_arr[i++] = digit;
cur_nodep = cur_nodep->restp;
}
}
最后我的新排序函数现在可以对相同数字的整数进行排序.这样， numbers[7] = {112,133,122,334,345,447,346};
Finally my new sorting function which is now sorts the integers in same digit. Such that, numbers[7] = {112,133,122,334,345,447,346};
queue_t * radix_sort(int *arr, const int size,queue_t *sorted_arr[]) {
int i, digit[size], initials[size],j;
for(i=0;i<size;i++)
initials[i] = arr[i];
i = 0;
while(initials[i] != 0){
j = i;
printf("initialssss%d", initials[--j]);
back_to_ints(sorted_arr, initials);
for(i=0;i<size;i++){
digit[i] = initials[i] % 10;
switch (digit[i]) {
case 0:
add_to_q(sorted_arr, arr[i], 0);
break;
case 1:
add_to_q(sorted_arr, arr[i], 1);
break;
case 2:
add_to_q(sorted_arr, arr[i], 2);
break;
case 3:
add_to_q(sorted_arr, arr[i], 3);
break;
case 4:
add_to_q(sorted_arr, arr[i], 4);
break;
case 5:
add_to_q(sorted_arr, arr[i], 5);
break;
case 6:
add_to_q(sorted_arr, arr[i], 6);
break;
case 7:
add_to_q(sorted_arr, arr[i], 7);
break;
case 8:
add_to_q(sorted_arr, arr[i], 8);
break;
case 9:
add_to_q(sorted_arr, arr[i], 9);
break;
}
}
sorted_arr[10] = add_to_eleventh(sorted_arr);
i++;
}
return sorted_arr[10];
}
我部分解决了这个问题.如果你想以相同的数字对数字进行排序，它可以工作.否则，它失败.例如，您的输入是 112,133,122,334,345,447,346，那么结果将是 112 122 133 334 345 346 447.但是，如果用户想要对类似的东西进行排序(111,13,12,334,345,447,1)，它会给出 111 1 12 13 334 345 447.那么，我该如何克服这个问题.
I solved the question partially. If you want to sort the numbers in same digit, it works. Otherwise, it fails. For instance, your inputs are 112,133,122,334,345,447,346 then the result will be 112 122 133 334 345 346 447. But, if the user wants to sort something like that(111,13,12,334,345,447,1) it gives 111 1 12 13 334 345 447. So, how can I overcome this problem.
另外，我对头文件做了一些改动.
Also, I have changed my header file a bit.
#ifndef RADIX_H_
#define RADIX_H_
typedef struct queue_node_s {
int element;
struct queue_node_s *restp;
}queue_node_t;
typedef struct {
queue_node_t *frontp,
*rearp;
int size;
}queue_t;
queue_t * radix_sort(int *arr,const int size, queue_t *sorted_arr[]);
void add_to_q(queue_t *queue_arr[], int value, int pos);
queue_t * add_to_eleventh(queue_t *queue[]);
void back_to_ints(queue_t *arr[], int *new_arr);
void displayRadixed(queue_t *sorted[]);
#endif /* RADIX_H_ */
感谢您重新打开我的帖子...
Thank you for reopening my thread...
推荐答案
我稍微修改了你的队列.为了更好地理解代码，我使用了front和rear作为全局变量.
I've modified your queue a bit. To better understand the code, I use front and rear as global variables.
typedef struct queue *queue_ptr;
struct queue {
int data;
queue_ptr next;
};
queue_ptr front[10], rear[10]; /* For base 10, The 11th queue is not needed */
于是加入队列的操作就变成了
So the operation of adding to queue becomes
void add_queue(int i, int data) {
queue_ptr tmp;
tmp = (queue_ptr) malloc(sizeof(*tmp));
tmp->next = NULL;
tmp->data = data;
if (front[i]) {
rear[i]->next = tmp;
} else {
front[i] = tmp;
}
rear[i] = tmp;
}
并添加一个从队列中删除的操作(也返回数据)
And add an operation of deleting from a queue(return the data as well)
int delete_queue(int i) {
int data;
queue_ptr tmp;
tmp = front[i];
if (!tmp) {
return -1; /* So that we can check if queue is empty */
}
data = tmp->data;
front[i] = tmp->next;
free(tmp);
return data;
}
所以现在我们可以实现基数排序了.使用实际数字而不是单个数字将数据移入队列可能更容易.请注意，如果您可以修改测试数组 *arr，则不需要第 11 个队列，并且您的 radix_sort 函数可能是这样的:
So now we can implement the radix sort. It may be easier to move your data into queue with the actual numbers rather than a single digit. Note that the 11th queue is not needed if you can modify your test array *arr, and your radix_sort function could be like this:
void radix_sort(int *arr, const int size) {
int i, j, k, radix, digits, tmp;
if (size < 1) {
return; /* don't do anything if invalid size */
}
/* get the number of digits */
for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *= 10);
/* perform sort (digits) times from LSB to MSB */
for (i = 0, radix = 1; i < digits; i++, radix *= 10) {
/* distribute into queues */
for (j = 0; j < size; j++) {
add_queue((arr[j] / radix) % 10, arr[j]);
}
/* take them out from each queue to the original test array */
for (j = 0, k = 0; j < 10; j++) {
for (tmp = delete_queue(j); tmp != -1;
tmp = delete_queue(j), k++) {
arr[k] = tmp;
}
}
}
}
最后你可以通过调用radix_sort(your_array, your_array_size)进行测试，完整代码是
And finally you can test by calling radix_sort(your_array, your_array_size), the full code is
#include <stdio.h>
#include <stdlib.h>
typedef struct queue *queue_ptr;
struct queue {
int data;
queue_ptr next;
};
queue_ptr front[10], rear[10]; /* For base 10, The 11th queue is not needed */
void add_queue(int i, int data) {
queue_ptr tmp;
tmp = (queue_ptr) malloc(sizeof(*tmp));
tmp->next = NULL;
tmp->data = data;
if (front[i]) {
rear[i]->next = tmp;
} else {
front[i] = tmp;
}
rear[i] = tmp;
}
int delete_queue(int i) {
int data;
queue_ptr tmp;
tmp = front[i];
if (!tmp) {
return -1; /* So that we can check if queue is empty */
}
data = tmp->data;
front[i] = tmp->next;
free(tmp);
return data;
}
void radix_sort(int *arr, const int size) {
int i, j, k, radix, digits, tmp;
if (size < 1) {
return; /* don't do anything if invalid size */
}
/* get the number of digits */
for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *=10);
/* perform sort (digits) times from LSB to MSB */
for (i = 0, radix = 1; i < digits; i++, radix *= 10) {
/* distribute to queues */
for (j = 0; j < size; j++) {
add_queue((arr[j] / radix) % 10, arr[j]);
}
/* take them out from each queue to the original test array */
for (j = 0, k = 0; j < 10; j++) {
for (tmp = delete_queue(j); tmp != -1;
tmp = delete_queue(j), k++) {
arr[k] = tmp;
}
}
}
}
int main(void) {
int i;
int a[5] = {133, 34, 555, 111, 12},
b[12] = {1, 1, 1, 4, 5, 6, 7, 8, 9, 11, 11, 12};
radix_sort(a, 5);
radix_sort(b, 5);
for (i = 0; i < 5; i++) {
printf("%d ", a[i]);
}
printf("
");
for (i = 0; i < 12; i++) {
printf("%d ", b[i]);
}
printf("
");
return 0;
}
输出是
12 34 111 133 555
1 1 1 4 5 6 7 8 9 11 11 12
这篇关于使用队列进行基数排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
