راديكس فرز تنفيذها في C ++

Question

أحاول تحسين بلدي C ++ عن طريق إنشاء برنامج سيأخذ كمية كبيرة من الأرقام بين 1 و 10 ^ 6. الدلاء التي ستتخزين الأرقام في كل تمريرة هي صفيف من العقد (حيث العقدة هي بنية قمت بإنشائها تحتوي على قيمة وسمة العقدة التالية).

بعد فرز الأرقام إلى دلاء وفقا لأقل قيمة كبيرة، لدي نقطة دلو واحدة إلى بداية دلو آخر (حتى أتمكن من الحصول على الأرقام التي يمكن تخزينها بسرعة دون تعطيل الطلب). لا يحتوي الشفونة الخاصة بي على أخطاء (إما تجميعها أو وقت التشغيل)، لكنني أصابت جدارا فيما يتعلق بكيفية حل التكرارات الستة المتبقية (لأنني أعرف مجموعة الأرقام).

المشكلة التي أحصل عليها هي في البداية تم توفير الأرقام إلى وظيفة radixsort في شكل صفيف int. بعد التكرار الأول للفرز، يتم الآن تخزين الأرقام في صفيف الهيكل. هل هناك أي طريقة يمكن أن أتمكن من إعادة صياغة التعليمات البرمجية الخاصة بي بحيث لدي واحدة فقط لحلقة للاتكرارات 7، أو سأحتاج إلى واحدة للحلقة التي سيتم تشغيلها مرة واحدة، وحلقة أخرى تحتها والتي سيتم تشغيلها 6 مرات قبل إرجاع المرتبة بالكامل قائمة؟

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
    int value;
    node *next; 
};

//The 10 buckets to store the intermediary results of every sort
node *bucket[10];
//This serves as the array of pointers to the front of every linked list
node *ptr[10];
//This serves as the array of pointer to the end of every linked list
node *end[10];
node *linkedpointer;
node *item;
node *temp;

void append(int value, int n)
{
    node *temp; 
    item=new node;
    item->value=value;
    item->next=NULL;
    end[n]=item;
    if(bucket[n]->next==NULL)
    {
        cout << "Bucket " << n << " is empty" <<endl;
        bucket[n]->next=item;
        ptr[n]=item;
    }
    else
    {
        cout << "Bucket " << n << " is not empty" <<endl;
        temp=bucket[n];
        while(temp->next!=NULL){
            temp=temp->next;
        }
        temp->next=item;
    }
}

bool isBucketEmpty(int n){
    if(bucket[n]->next!=NULL)
        return false;
    else
        return true;
}
//print the contents of all buckets in order
void printBucket(){
    temp=bucket[0]->next;
    int i=0;
    while(i<10){
        if(temp==NULL){
            i++;
            temp=bucket[i]->next;                       
        }
        else break;

    }
    linkedpointer=temp;
    while(temp!=NULL){
        cout << temp->value <<endl;
        temp=temp->next;
    }
}

void radixSort(int *list, int length){
    int i,j,k,l;
    int x;
    for(i=0;i<10;i++){
        bucket[i]=new node;
        ptr[i]=new node;
        ptr[i]->next=NULL;
        end[i]=new node;
    }
    linkedpointer=new node;

    //Perform radix sort
    for(i=0;i<1;i++){
        for(j=0;j<length;j++){          
            x=(int)(*(list+j)/pow(10,i))%10;            
            append(*(list+j),x);
            printBucket(x); 
        }//End of insertion loop
        k=0,l=1;

        //Linking loop: Link end of one linked list to the front of another
        for(j=0;j<9;j++){
            if(isBucketEmpty(k))
                k++;
            if(isBucketEmpty(l) && l!=9)
                l++;
            if(!isBucketEmpty(k) && !isBucketEmpty(l)){
                end[k]->next=ptr[l];
                k++;
                if(l!=9) l++;   
            }

        }//End of linking for loop

        cout << "Print results" <<endl;
        printBucket();

        for(j=0;j<10;j++)
            bucket[i]->next=NULL;                       
        cout << "End of iteration" <<endl;
    }//End of radix sort loop
}

int main(){
    int testcases,i,input;
    cin >> testcases;
    int list[testcases];
    int *ptr=&list[0];
    for(i=0;i<testcases;i++){
        cin>>list[i];
    }

    radixSort(ptr,testcases);
    return 0;
}

Answer 1

أعتقد أنك غير مرتبط بشدة في الحل الخاص بك. يمكنك تطبيق Radix باستخدام مجموعة واحدة المستلمة في الإدخال، مع الدلاء في كل خطوة ممثلة بمجموعة من المؤشرات التي تحمل مؤشر بدء تشغيل كل دلو في صفيف الإدخال.

في الواقع، يمكنك حتى القيام بذلك بشكل متكرر:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

بالتاكيد buckets[i+1] - buckets[i] سوف تسبب تجاوزا مؤقتا عندما i هو 9، لكنني حذفت الفحص الإضافي أو قابلية القراءة؛ أنا أثق بك تعرف كيفية التعامل مع ذلك.

مع ذلك، عليك فقط الاتصال radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) وينبغي فرز صفيفك.

Answer 2

لتسريع العملية بأفضل إدارة الذاكرة، قم بإنشاء مصفوفة للتهم التي يتم تحويلها إلى مؤشرات عن طريق إجراء تمرير واحد عبر الصفيف. تخصيص مجموعة temp ثانية نفس الحجم مثل الصفيف الأصلي، وترتيب radix بين الصفيفين حتى يتم فرز الصفيف. إذا تم تنفيذ عدد فردي من تصاريح راديكس، فسيلزم نسخ صفيف Temp إلى الصفيف الأصلي في النهاية.

لتسريع العملية، استخدم Base 256 بدلا من قاعدة 10 لفرز Radix. يستغرق هذا فقط 1 مرة المسح الضوئي لإنشاء مصفوفة و 4 راديكس فرز يمر للقيام بالفرز. رمز المثال:

typedef unsigned int uint32_t;

uint32_t * RadixSort(uint32_t * a, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
uint32_t * b = new uint32_t [COUNT];    // allocate temp array
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    delete[] b;
    return(a);
}

Answer 3

منذ قيمك هي ITS في نطاق 0 ... 1،000،000

يمكنك إنشاء مجموعة int من الحجم 1000،001، والقيام بأكمله في مرورين

init الصفيف الثاني لجميع الأصفار.

قم بعمل تمرير من خلال صفيف الإدخال الخاص بك، واستخدم القيمة كضمان لزيادة القيمة في الصفيف الثاني.

بمجرد أن تفعل ذلك، فإن المرور الثاني سهل. المشي من خلال الصفيف الثاني، ويخبرك كل عنصر بعدد مرات ظهور هذا الرقم في الصفيف الأصلي. استخدم هذه المعلومات لإعادة فتح صفيف الإدخال الخاص بك.