c - キューを使用した基数ソート

Question

キューを使用して基数ソートの実装を作成したいと考えていました。

コードのどの部分に問題があるのか​​、どのリソースを読むべきなのかがわかりませんでした。私のコードは完全に間違っているかもしれませんが、これは何の助けも借りずに実装したものです (データ構造とアルゴリズムのコースはまだ受講していません)。

関数を作成しましたが、機能しませんでした。調査中にいくつかのコード サンプルを見ましたが、私にとってはもっと複雑に思えました。

まず、すべての整数の最下位桁を見つけたいと思いました 。次に、添字が一致するキュー要素でそれらをソートし、 ソート後にすべてのキューを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 関数を作成し、コードの重複を取り除くのに役立ちました。ところで、James Khoury の方法は最も単純なものですが、ここでも再帰を使用しています。

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

次に、他のヘルパー関数を作成しました。1 つは add_to_eleventh で、単純にすべてのキュー要素を 11 番目のキューの後方に追加します。私の意見では、質問が望んでいることをやっています。

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

3番目に、最後のヘルパー関数は back_to_ints です。その目的は、11 番目のキューの要素を取得し、それらを 10 で割り、整数配列で返すことです。

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

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

スレ開き直してくれてありがとう…

Answer 1

キューを少し変更しました。コードをよりよく理解するために、フロントとリアをグローバル変数として使用します。

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

これで、基数ソートを実装できます。データを 1 桁ではなく実際の数値でキューに移動する方が簡単な場合があります。テスト配列 *arr を変更できる場合、11 番目のキューは必要ないことに注意してください。radix_sort 関数は次のようになります。

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) を呼び出してテストできます。完全なコードは次のとおりです。

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

そして出力は

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

Answer 2

ここですでにいくつかの良い情報。より高いレベルでは、コードが必要以上に複雑になるため、コードのデバッグが困難になります。以下は、C を使用してより慣用的なスタイルでアルゴリズムを表現する別のコードです。

全体的なポイントは、コードに関しては、通常は少ないほど良いということです。単純さはあなたの友達です. ここに示す機能:

1. キューの循環単一リンク リスト。キューは、リストの末尾ノードへのポインターです。これにより、追加と連結は高速な定数時間操作になります。
2. 論理的で再利用可能な機能分解。
3. 簡単なテストを含めて約 80 の SLOC のみ。ソート機能は18SLOC。
4. 軽くテストしました。

並べ替えは次のとおりです。

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

そして残り：

#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.

小さなテストメイン:

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

Answer 3

私が最初のコードサンプルで見た問題は、

curNum = curNodep-> element.key

curNumには常に完全な数値があり、switchステートメントは常に curNum％10を実行します。これは、最後の桁のみをテストします。

再帰ソリューション（再帰は問題ではありません）では、パラメーターを渡して、どの桁を処理する必要があるかを知る必要があります。

私はこのテクニックをイマージョンとして知っています。

回答の最後に置いたサンプルを見ると、最後の桁が順序付けであることがわかります。入力サンプルを変更して、これをよりよく確認できます。最後の数字が小さい大きな数字を追加します（例「901」）。結果を参照してください。

私の英語でごめんなさい...

Answer 4

免責事項: 以前に基数ソートを実装したり、以下のコードをテストしたりしていません。演習としてお任せします。

何かを何度もコピーして貼り付けていることに気付いたら、立ち止まって考えてみてください。パターンがあるに違いありません。

あなたの switch ステートメントは、多くのコピーと貼り付けです。case 1:あなたには次の行があります：

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

私はそれがそうであるべきだと思います：

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

このコードをリファクタリングした場合、これをより簡単に確認できたでしょうか?

switch ステートメント全体を次のように置き換えるとどうなりますか。

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