Lsd radix sort + подсчет путаницы

У меня работает основанная на битах сортировка 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?

0

Решение

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

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

Других решений пока нет …

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