Сортировка по основанию с использованием очереди

Я хотел создать реализацию сортировки по основанию с использованием очередей.

Я не мог понять, в какой части моего кода есть проблемы или какие ресурсы я должен прочитать. Мой код может быть совершенно неправильным, но это моя реализация без какой-либо помощи (я еще не прошел курс по структурам данных и алгоритмам).

Я создал функцию, но она не сработала. Во время исследования я видел несколько примеров кода, но они показались мне более сложными.

Во-первых я хотел найти наименьшую значащую цифру всех целых чисел Затем отсортировать их в элементе очереди, индекс которого совпадает, затем после сортировки скопировать все очереди в конец 11-го элемента очереди. Повторите эту сортировку в 11-м элементе очереди, пока не достигнете старшей значащей цифры.

Я смог найти младшую значащую цифру. И отсортировать по этой цифре. Но я не мог анализировать другие цифры. Например; Я мог бы отсортировать 1, 2, 4, 5, 3, но когда приходит время отсортировать 2 или более цифр, это не удается...

Надеюсь, я был понятен и кратко объяснил свою проблему.

// 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, и он дал мне несколько инструкций, чтобы сделать мой код более понятным.

Я разделил свою функцию на функции, а также перестал использовать рекурсию.

Во-первых, я создал функцию add_to_q, которая добавляет значение в связанную очередь, и это помогло избавиться от дублирования кода. Кстати, способ Джеймса Хури самый простой, но он опять же использует рекурсию.

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, который просто добавляет все элементы очереди в конец одиннадцатой очереди. На мой взгляд, он делает то, что хочет вопрос.

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-й очереди, разделить их на десять и вернуть их в виде целочисленного массива.

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;
}
}

Наконец моя новая функция сортировки, которая теперь сортирует целые числа по одной и той же цифре. Таким образом, числа [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. Итак, как я могу победить эту проблему.

Кроме того, я немного изменил свой заголовочный файл.

#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_ */

Спасибо, что снова открыли мою тему...