Radix Sort, реализованный в C++

Question

Я пытаюсь улучшить свой C++, создав программу, которая будет принимать большое количество чисел от 1 до 10^6. Ведра, которые будут хранить числа в каждом проходе, представляют собой массив узлов (где узел представляет собой созданную мной структуру, содержащую значение и атрибут следующего узла).

После сортировки чисел в ведрах по наименее значащему значению у меня есть конец одной ведомой точки к началу другого ведра (чтобы я мог быстро получить сохраненные числа без нарушения порядка). У моего кода нет ошибок (компиляция или время выполнения), но я ударил стену относительно того, как я собираюсь решить оставшиеся 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

Поскольку ваши значения Интс в диапазоне 0 ... 1000000

Вы можете создать Int массив размера 1,000,001, и сделать все это за два прохода

Init второй массив все нули.

Пройдите через ваш входной массив и используйте значение в качестве индекса , чтобы увеличить значение во втором массиве.

Как только вы это сделаете, второй проход прост. Пройдите второй массив, и каждый элемент сообщает вам, сколько раз в исходном массиве появилось число . Используйте эту информацию, чтобы заполнить ваш входной массив.

Answer 3

Чтобы ускорить процесс с улучшенным управлением памятью, создайте матрицу для счетчиков, которые преобразуются в индексы, делая один проход по массиву. Выделите второй массив тем тем же самым размером, что и исходный массив, и соберите radix между двумя массивами до тех пор, пока массив не будет отсортирован. Если выполняется нечетное число проходов сортировки радикса, тогда массив temp необходимо будет скопировать обратно в исходный массив в конце.

Чтобы ускорить процесс, используйте основание 256 вместо основания 10 для сортировки по основанию. Для выполнения этой сортировки требуется всего 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); 
}