Radix Sort используя очереди

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

#include <iostream>
#include <queue>
#include <ctime>
#include <cstdlib>
using namespace std;

int *radixSort(int q[]);

int main() {
const int MAX=1000;
int radix[MAX], *sortedRadix;
int seed =time(0);
srand(seed);//fill array with random #s
for (int i=0;i<MAX;i++){
int num=0+rand()%MAX;
radix[i]=num;
}
//print unsorted
for (int j=0;j<MAX;j++)
cout << radix[j] << " ";
cout << endl << endl;
//radix sort
sortedRadix=radixSort(radix);
//print sorted
for (int j=0;j<MAX;j++)
cout << sortedRadix[j] << " ";

cout << endl <<endl;
cout<<"flag";return 0;
}

int *radixSort(int q[]) {
queue<int> bins[10]; //one array per possible digit
int maxDigits=3; //holds amount of digits in largest number
int currentDigit=1; //right most digit
int a[1000]; //holds numbers during sort

while (currentDigit <= maxDigits) {
for(int i=0; i<1000; i++){ //loop through whole array
int num = q[i]; //set to current value of array position
int digitValue = static_cast<int>(num/currentDigit)%10; //get the decimal digit at current digit
bins[digitValue].push(num); //put digits in corresponding bins
}
//Transfer results of bins back into main array
for (int j=0; j<1000; j++){
for(int k=0;k<10;k++){ //loop through all bins
while (!bins[k].empty()){ //push all elements in bin[k] until empty to a
int temp=bins[k].front();
a[j]=temp;
bins[k].pop();
}
}
}
currentDigit++;
}
return a;
}

0

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]