У меня работает основанная на битах сортировка LSD, но я не совсем понимаю, что мне нужно сделать, чтобы заставить его работать. В моей функции LSD_radixsort r — мой максимальный бит, представленный битами = (2 ^ r) -1. Мой цикл for проходит до тех пор, пока бит / exp> 0. Хотя, когда я делаю биты как тип int, он не полностью сортирует мой массив. Когда я делаю это вдвойне, это все сортирует. Если я имею дело с десятичными числами, цикл никогда не прервется, так как это всегда будет какое-то небольшое число, которое больше 0? Вот мой код:
#include "lab8.h"#include <iostream>
using namespace std;
void countSort2(unsigned int arr[], int n, int exp);
unsigned int getMax(unsigned int arr[], int n);
void LSD_radixSort (unsigned int * A, int size, int r)
{// Find the maximum number to know number of digits
double bits = pow(2,r)-1;// Do counting sort for every digit.
for (int exp = 1; bits/exp > 0; exp *= 2)
{
countSort2(A, size, exp);
}}void countSort2(unsigned int arr[], int n, int exp)
{
int *output = new int[n]; // output array
int i, count[2] = {0};// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%2 ]++;
// Change count[i] so that count[i] now contains actual position of
// this digit in output[]
for (i = 1; i < 2; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%2 ] - 1] = arr[i];
count[ (arr[i]/exp)%2 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];}int main()
{
unsigned int b[10] = {43,351,25,24,52,65,43,1,4,9};
LSD_radixSort(b,10,5);
int i = 0;
while(i<10)
{
cout<<b[i]<<endl;
i++;
}
system("pause");
}
Когда я запускаю его с двойными битами, мой выходной массив = 1,4,9,24,25,43,43,52,65,351
Когда я запускаю его с битами int, мой выходной массив = 65,1,4,9,43,43,52,24,25,351
Есть идеи, почему это происходит? Разве я не хочу, чтобы мой тип был int?
Задача ещё не решена.
Других решений пока нет …