Radix Sortierung mit der Warteschlange

Question

Ich wollte eine radix sort Implementierung mit Warteschlangen erstellen.

Ich konnte nicht herausfinden, welcher Teil meines Codes Probleme hat oder welche Ressourcen ich lesen sollte. Mein Code kann völlig falsch sein, aber das ist meine Implementierung ohne Hilfe (Ich habe noch keine Datenstrukturen & Algorithmen natürlich genommen).

Ich habe eine Funktion erstellt, aber es hat nicht funktioniert. Während ich recherchierte, sah ich einige Code-Beispiele, aber sie schienen für mich komplexer zu sein.

Zum einen Ich wollte die niedrigstwertige Stelle aller ganzen Zahlen Dann sortieren sie in der Warteschlange Element, dessen Index Übereinstimmungen finden, dann nach Art alle Warteschlangen kopieren des 11. Warteschlangenelement zu beenden. Sortiere das Element in der 11. Warteschlange erneut, bis die höchstwertige Ziffer erreicht ist.

Ich könnte die niedrigste Ziffer finden. Und sortiere nach dieser Ziffer. Aber ich konnte keine anderen Ziffern analysieren. Zum Beispiel; Ich könnte 1, 2, 4, 5, 3 sortieren, aber wenn die Zeit kommt, um 2 oder mehr Ziffern zu sortieren, schlägt es fehl ...

Ich hoffe, ich war klar und erklärte mein Problem kurz.

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

Edit 1 (Made einige Fortschritte)

ich Vorschläge von William Morris gefolgt. Ich musste dieselbe Frage bei CodeReview stellen und er gab mir einige Anweisungen, um meinen Code klarer zu machen.

Ich habe meine Funktion in Funktionen aufgeteilt und auch die Rekursion gestoppt.

Zuerst, ich habe eine add_to_q-Funktion erstellt, die Wert zu verwandten Warteschlange und es half, die Code-Duplizierung loszuwerden. Übrigens ist James Khourys Weg der einfachste, aber er benutzt wieder Rekursion.

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

Zweitens Ich habe andere Hilfsfunktionen. Einer ist add_to_elect, der einfach alle Warteschlangenelemente zu der elften Queue hin hinzufügt. Meiner Meinung nach tut es was die Frage will.

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

Drittens, meine letzte Hilfsfunktion ist back_to_ints. Sein Zweck ist, die Elemente in der elften Warteschlange aufzunehmen und sie durch zehn zu teilen und sie in einem Integer-Array zurückzugeben.

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

Schließlich meine neue Sortierfunktion, die jetzt sortiert die ganzen Zahlen in derselben Ziffer. So dass Zahlen [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]; 
} 

Ich löste die Frage teilweise. Wenn Sie die Zahlen in derselben Ziffer sortieren möchten, funktioniert es. Sonst schlägt es fehl. Zum Beispiel sind Ihre Eingaben 112,133,122,334,345,447,346, dann wird das Ergebnis sein.Aber, wenn der Benutzer etwas wie die (111,13,12,334,345,447,1) sortieren will es gibt . Also, wie kann ich dieses Problem überwinden?

Auch ich habe meine Header-Datei ein wenig geändert.

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

Vielen Dank für meinen Thread Wiedereröffnung ...

Answer 1

Haftungsausschluss: Ich habe eine Radixsort bevor nicht implementiert oder den Code getestet. Das überlasse ich dir als Übung.

Wenn Sie sich mehr als einmal etwas kopieren-einfügen finden, denken Sie daran: Es muss ein Muster geben.

Ihre switch-Anweisung ist eine Menge Kopie-Einfügen. In case 1: haben Sie eine Linie:

queue[1]->frontp = queue[0]->rearp; 

Ich vermute, es sein sollte:

queue[1]->frontp = queue[1]->rearp; 

Wenn Sie diesen Code wieder einkalkuliert hatte man diese leichter zu sehen waren in der Lage kann?

Was ist die gesamte Switch-Anweisung zu ersetzen mit:

int leastSignificantDigit = curNum%10; 

if(queue[leastSignificantDigit]->size == 0){ 
    queue[leastSignificantDigit]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
    queue[leastSignificantDigit]->frontp = queue[leastSignificantDigit]->rearp; 
} else { 
    queue[leastSignificantDigit]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
    queue[leastSignificantDigit]->rearp = queue[leastSignificantDigit]->rearp->restp; 
} 
++(queue[leastSignificantDigit]->size); 
queue[leastSignificantDigit]->rearp->element = curNodep->element; 
queue[leastSignificantDigit]->rearp->restp = NULL; 
radixSort(curNodep->restp, queue, size); 

Answer 2

Das Problem, das ich in der ersten Codebeispiel gesehen haben, ist, dass

curNum = curNodep-> element.key

curNum haben immer die volle Zahl und die switch-Anweisung immer tun curNum% 10, und dies nur Test de letzten Ziffer.

In Ihrer Rekursionslösung (Rekursion ist kein Problem) müssen Sie einen Parameter übergeben, um zu wissen, welche Ziffer es zu behandeln hat.

Ich weiß, diese Technik als Untertauchen.

Wenn Sie die Beispiele sehen, die Sie am Ende der Antwort eingefügt haben, können Sie sehen, dass die letzte Ziffer der Besteller ist. Sie können die Eingabe-Beispiele ändern, um dies besser zu sehen. Fügen Sie große Zahlen mit einer kleinen letzten Zahl hinzu, Beispiel '901', und sehen Sie das Ergebnis.

Entschuldigung für mein Englisch ...

Answer 3

Ich habe Ihre Warteschlange ein wenig geändert. Um den Code besser zu verstehen, verwende ich vorne und hinten als globale Variablen.

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 ist der Betrieb Warteschlange der Zugabe wird

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

Und fügen Sie eine Operation aus einer Warteschlange zu löschen (Rückkehr als auch die Daten)

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

So, jetzt können wir implementieren die Radix-Sortierung. Es kann einfacher sein, Ihre Daten in die Warteschlange mit den tatsächlichen Zahlen als einer einzelnen Ziffer zu verschieben.Beachten Sie, dass die 11. Warteschlange nicht erforderlich, wenn Sie Ihre Test Array ändern können * arr, und Ihre radix_sort Funktion wie folgt sein könnte:

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

Und schließlich können Sie testen, indem Aufruf radix_sort (your_array, your_array_size), die volle Code ist

#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("\n"); 

     for (i = 0; i < 12; i++) { 
       printf("%d ", b[i]); 
     } 
     printf("\n"); 

     return 0; 
} 

und der Ausgang ist

12 34 111 133 555 
1 1 1 4 5 6 7 8 9 11 11 12 

Answer 4

Einige gute Informationen hier bereits. Auf einer höheren Ebene wird es schwierig sein, Ihren Code zu debuggen, weil er komplexer ist als er sein muss. Unten ist ein anderer Code, der C verwendet, um den Algorithmus in einem mehr idiomatischen Stil auszudrücken.

Der allgemeine Punkt ist, dass, wenn es um Code geht, weniger ist in der Regel mehr: Einfachheit ist dein Freund. Die hier gezeigten Funktionen:

1. Kreisförmig einfach verkettete Listen für Warteschlangen. Eine Warteschlange ist ein Zeiger auf den Endknoten der Liste. Append und Verketten sind dabei schnelle Konstant-Zeit-Operationen.
2. Logische, wiederverwendbare funktionelle Zerlegung.
3. Nur etwa 80 SLOC einschließlich eines einfachen Tests. Die Sortierfunktion ist 18 SLOC.
4. Leicht getestet.

Hier ist die Art:

// Radix sort the given queue. 
void sort(QUEUE *queue) 
{ 
    unsigned i, j, div; 
    QUEUE queues[RADIX], accum; 

    // Handle case of nothing to sort. 
    if (*queue == NULL) return; 

    // Accumulator queue initially holds unsorted input. 
    accum = *queue; 

    // Make one pass per radix digit. 
    for (i = 0, div = RADIX; i < MAX_DIGITS; i++, div *= RADIX) { 

    // Clear the radix queues. 
    for (j = 0; j < RADIX; j++) queues[j] = NULL; 

    // Append accumulator nodes onto radix queues based on current digit. 
    NODE *p = accum, *p_next = p->next; 
    do { 
     // Save p->next here because append below will change it. 
     p = p_next; p_next = p->next; 
     append_node(&queues[p->val/div % RADIX], p); 
    } while (p != accum); 

    // Gather all the radix queues into the accumulator again. 
    for (accum = NULL, j = 0; j < RADIX; j++) cat(&accum, queues[j]); 
    } 
    // Accumulator now holds sorted input. 
    *queue = accum; 
} 

Und der Rest:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define RADIX 10 
#define MAX_DIGITS 9 

// Node and circular queue. A queue is either null or a pointer to the _tail_ node. 
typedef struct node_s { 
    struct node_s *next; 
    unsigned val; 
} NODE, *QUEUE; 

// Make a new node with given value. 
NODE *new_node(unsigned val) 
{ 
    NODE *node = calloc(1, sizeof *node); 
    // Must trap null return value here in production code! 
    node->val = val; 
    return node; 
} 

// Append given node to the tail of a queue. 
void append_node(QUEUE *queue, NODE *node) 
{ 
    NODE *tail = *queue; 
    if (tail) { 
    node->next = tail->next; 
    tail->next = node; 
    } 
    else { 
    node->next = node; 
    } 
    *queue = node; 
} 

// Concatenate the second queue onto the tail of the first. 
// First queue is changed (because it's a pointer to a tail node). 
void cat(QUEUE *a, QUEUE b_tail) 
{ 
    NODE *a_tail, *a_head; 

    if (b_tail == NULL) return; 
    a_tail = *a; 
    if (a_tail) { 
    a_head = a_tail->next; 
    a_tail->next = b_tail->next; 
    b_tail->next = a_head; 
    } 
    *a = b_tail; 
} 
// Sort code above goes here if you're compiling it. 
// And test main goes here. 

Ein kleiner Test: ca.

int main(void) 
{ 
    int i; 
    unsigned data[] = { 98, 111, 42, 1111, 21 , 997, 0, 99999, 20903}; 

    // Make a queue from data. 
    QUEUE a = NULL; 
    for (i = 0; i < sizeof data/sizeof data[0]; i++) 
    append_node(&a, new_node(data[i])); 

    sort(&a); 

    // Print the circular list. 
    NODE *p = a; 
    do { 
    p = p->next; 
    printf("%u\n", p->val); 
    } while (p != a); 

    return 0; 
}