Radix Sort реализована в C++
Я пытаюсь улучшить свой C++, создав программу, которая будет принимать большое количество чисел от 1 до 10^6. Группы, в которых будут храниться числа на каждом проходе, представляют собой массив узлов (где узел - это созданная мной структура, содержащая значение и атрибут следующего узла).
После сортировки чисел в сегменты по наименее значимому значению у меня есть конец одной точки сегмента к началу другого сегмента (чтобы я мог быстро получить сохраняемые номера без нарушения порядка). В моем коде нет ошибок (ни во время компиляции, ни во время выполнения), но я столкнулся с проблемой того, как я собираюсь решить оставшиеся 6 итераций (так как я знаю диапазон чисел).
Проблема, с которой я столкнулся, заключается в том, что изначально числа были переданы функции radixSort в виде массива int. После первой итерации сортировки числа теперь сохраняются в массиве структур. Есть ли способ, которым я мог бы переделать свой код так, чтобы у меня был только один цикл for для 7 итераций, или мне понадобится один цикл for, который будет выполняться один раз, и еще один цикл под ним, который будет выполняться 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;
}
3 ответа
Я думаю, что вы сильно усложняете свое решение. Вы можете реализовать основание, используя единственный массив, полученный на входе, с сегментами на каждом шаге, представленными массивом индексов, которые отмечают начальный индекс каждого сегмента во входном массиве.
На самом деле, вы могли бы даже сделать это рекурсивно:
// 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)
и ваш массив должен быть отсортирован.
Чтобы ускорить процесс с улучшенным управлением памятью, создайте матрицу для подсчетов, которые преобразуются в индексы путем одного прохода по массиву. Выделите второй временный массив того же размера, что и исходный массив, и делайте радикальную сортировку между двумя массивами, пока массив не будет отсортирован. Если выполняется нечетное число проходов радикальной сортировки, то в конце необходимо будет скопировать временный массив обратно в исходный массив.
Чтобы еще больше ускорить процесс, используйте базу 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);
}
Поскольку ваши значения - это целые числа в диапазоне 0 ... 1 000 000
Вы можете создать массив размером 1 000 001 и сделать все за два прохода
Инициируйте второй массив со всеми нулями.
Сделайте проход через ваш входной массив и используйте значение в качестве индекса, чтобы увеличить значение во втором массиве.
Как только вы это сделаете, второй проход будет легким. пройти через второй массив, и каждый элемент сообщает вам, сколько раз это число появилось в исходном массиве. Используйте эту информацию для повторного заполнения вашего входного массива.