単独リンクリストでのソートのカウントC＃

Question

単独リンクリストでカウントソートを行う方法はありますか？私は例を見ていないし、それらなしでそれを作ることは非常に難しいです。私は配列の例を持っていて、単独でリンクされたリストでそれをしたいと思います。 誰かが単独でリンクしたリストでそれをしたことがありますか？

public static int[] CountingSortArray(int[] array) 
    { 
     int[] aux = new int[array.Length]; 

     // find the smallest and the largest value 
     int min = array[0]; 
     int max = array[0]; 
     for (int i = 1; i < array.Length; i++) 
     { 
      if (array[i] < min) min = array[i]; 
      else if (array[i] > max) max = array[i]; 
     } 

     int[] counts = new int[max - min + 1]; 

     for (int i = 0; i < array.Length; i++) 
     { 
      counts[array[i] - min]++; 
     } 

     counts[0]--; 
     for (int i = 1; i < counts.Length; i++) 
     { 
      counts[i] = counts[i] + counts[i - 1]; 
     } 

     for (int i = array.Length - 1; i >= 0; i--) 
     { 
      aux[counts[array[i] - min]--] = array[i]; 
     } 

     return aux; 
    } 

Answer 1

は私がアレイ上で動作するものが見つかりました：私はそれがリンクリストに変更することができ、最小限の労力で考えるhttp://www.geeksforgeeks.org/counting-sort/

を、唯一の問題は、あなたがリンクリストを横断終わるだろうということですランダムなアクセス権を持たないなど、何度も何度も使用しています。 []ではかなり効率的ではありません。あなたは私が入力を終えることができた前と同じことを見つけたように思えるので、私の答えはちょっと無意味だと思います。しかし、私はまだあなたが問題を抱えている場所について少し興味があります。

どこから始めるべきかを判断するヒント：問題がある場合：array[i]が使用されるたびに、i番目のアイテムを最初に取得する代わりに、リンクされたリストを最初にトラバースする必要があります。

編集：2番目にリンクされた頻度のリストを作成する必要がある唯一の理由は、実際に結果として得られるリンクリストで作業する必要がある場合です。表示目的のためにリンクされたリスト内の値のソートされたリストが必要な場合は、周波数を保持する配列が機能します（私は同時にすべての値の配列を作成してから、それ）。私はc、C++、C++/cxをどこかに混乱させてしまったことを謝りましたが（私はコンパイラをすぐに手に入れることはできません）、これはどうやって行うのがよいか分かります。

public static node* FindMin(node* root){ //FindMax would be nearly identical 
    node* minValue = root; 
    while(node->Next){ 
    if(node->Value < minValue->Value) 
     minValue = node; 
    } 
    return minValue; 
} 
public static node* CountingSortArray(node* linklist){ 
    node* root = linkedlist 

    node* min = FindMin(linklist); 
    node* max = FindMax(linklist); 

    int[] counts = new int[max->Value - min->Value + 1]; 

    while(root != NULL){ 
    counts[root->Value] += 1; 
    root = root->Next; 
    } 

    int i = 0; 
    root = linkedlist; 

    while(ptr != NULL){ 
    if(counts[i] == 0) 
     ++i; 
    else{ 
     root->Value = i; 
     --count[i]; 
     root = root->Next; 
    } 
    } 
} 

void push(node** head, int new_data){ 
    node* newNode = new node(); 

    newNode->Value = new_data; 
    newNode->Next = (*head); 
    (*head) = newNode; 
} 

void printList(node* root){ 
    while(root != NULL){ 
    printf(%d ", root->Value); 
    root = root->Next; 
    } 
    printf("\n"); 
} 

int main(void){ 
    node* myLinkedList = NULL; 
    push(&head, 0); 
    push(&head, 1); 
    push(&head, 0); 
    push(&head, 2); 
    push(&head, 0); 
    push(&head, 2); 

    printList(myLinkedList); 
    CountingSortArray(myLinkedList); 
    printList(myLinkedList); 
} 

Answer 2

この例のコードは、基数（max-min + 1）の基数ソートによく似ています。通常、カウントソートは以下のコードのようになります。最小値と最大値を取得するには、リストをパスします。カウントを生成するために2回目のパスを作成します。カウントを渡して、（データをコピーする代わりに）カウントに基づいて新しい配列を生成します。コード例：

for (size_t i = 0; i < array.Length; i++) 
     counts[array[i]-min]++; 
    size_t i = 0; 
    for(size_t j = 0; j < counts.Length); j++){ 
     for(size_t n = counts[j]; n; n--){ 
      aux[i++] = j+min; 
     } 
    }