負の整数を含む整数の基数ソートを実装しようとしています。負でない int の場合、数字 0 ～ 9 に対応する 10 個のキューのキューを作成し、LSD アルゴリズムを実装することを計画していました。しかし、私は負の整数と混同していました。私が今考えているのは、それらのために 10 個のキューの別のキューを作成し、それらを個別に並べ替えてから、最後に、並べ替えられた負の整数を含むリストと非負の整数を含むリストの 2 つのリストを作成することです。そして最後に、それらをマージします。
これについてあなたはどう思いますか？負の整数を処理するより効率的な方法はありますか?
もう1つの解決策は、配列から負の整数を分離し、それらを正にし、基数を使用して正の値としてソートし、それを逆にして、ソートされた非負の配列を追加することです。
符号ビットは符号付き整数の最上位ビットですが、基数ソートではデフォルトですべての数値が符号なし整数として扱われることに注意してください。したがって、負の数は正の数よりも小さいことをアルゴリズムに伝える必要があります。32 ビットの符号付き整数の場合、最初に下位 3 バイトをソートし、次に符号ビットを反転して 4 番目 (上位) バイトをソートし、1 ではなく負の数に 0 が使用されるようにすることができます。
数値を 10 進数ではなくバイト単位でソートすることを強くお勧めします。これは、マシンが数字を抽出するよりもバイトを取得する方がはるかに簡単だからです。
絶対！もちろん、ポジティブなものからネガティブなものを分割することに注意する必要がありますが、幸いなことにこれは簡単です. ソート アルゴリズムの最初に、値 0 を中心に配列を分割するだけです。その後、分割の上下で基数ソートを行います。
これが実際のアルゴリズムです。これは、Kevin Wayne と Bob Sedgewick の MSD 基数ソートから導き出しました: http://algs4.cs.princeton.edu/51radix/MSD.java.html
private static final int CUTOFF = 15;
private static final int BITS_PER_INT = 32;
private static final int BITS_PER_BYTE = 8;
private static final int R = 256;
public void sort(int[] a){
int firstPositiveIndex = partition(0, a, 0, a.length-1);
int[] aux =new int[a.length];
if(firstPositiveIndex>0){
recSort(a, firstPositiveIndex, a.length-1, 0,aux);
recSort(a, 0, firstPositiveIndex-1, 0,aux);
}else{//all positive
recSort(a, 0, a.length-1, 0, aux);
}
}
private void recSort(int[] a, int lo, int hi, int d, int[] aux){
if(d>4)return;
if(hi-lo<CUTOFF){
insertionSort(a,lo, hi);
return;
}
int[] count = new int[R+1];
//compute counts
int bitsToShift = BITS_PER_INT-BITS_PER_BYTE*d-BITS_PER_BYTE;
int mask = 0b1111_1111;
for(int i = lo; i<=hi; i++){
int c = (a[i]>>bitsToShift) & mask;
count[c+1]++;
}
//compute indices
for(int i = 0; i<R; i++){
count[i+1]=count[i]+count[i+1];
}
//distribute
for(int i = lo; i<=hi; i++){
int c = (a[i]>>bitsToShift) & mask;
aux[count[c]+lo] = a[i];
count[c]++;
}
//copy back
for(int i = lo; i<=hi; i++){
a[i]=aux[i];
}
if(count[0]>0)
recSort(a, lo, lo+count[0]-1, d+1, aux);
for(int i = 1; i<R; i++){
if(count[i]>0)
recSort(a, lo+count[i-1], lo+count[i]-1, d+1, aux);
}
}
// insertion sort a[lo..hi], starting at dth character
private void insertionSort(int[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && a[j] < a[j-1]; j--)
swap(a, j, j-1);
}
//returns the index of the partition or to the right of where it should be if the pivot is not in the array
public int partition(int pivot, int[] a, int lo, int hi){
int curLo = lo;
int curHi = hi;
while(curLo<curHi){
while(a[curLo]<pivot){
if((curLo+1)>hi)return hi+1;
curLo++;
}
while(a[curHi]>pivot){
if((curHi-1)<lo)return lo-1;
curHi--;
}
if(curLo<curHi){
swap(a, curLo, curHi);
if(a[curLo]!=pivot)curLo++;
if(a[curHi]!=pivot)curHi--;
}
}
return curLo;
}
private void swap(int[] a, int i1, int i2){
int t = a[i1];
a[i1]=a[i2];
a[i2]=t;
}
おそらく、符号付きの値を処理する最も簡単な方法は、最上位桁を操作するときに累積の開始位置をオフセットすることです (つまり、位置オフセットの生成)。すべての数字が符号なしとして扱われるように入力を変換することもオプションですが、値配列に対して少なくとも 2 回 (1 回は入力を準備し、もう 1 回は出力を復元するために) 操作を適用する必要があります。
これは、最初の手法とバイト サイズの数字を使用します (一般に、バイト アクセスの方が効率的です)。
void lsdradixsort(int* a, size_t n)
{
// isolate integer byte by index.
auto bmask = [](int x, size_t i)
{
return (static_cast<unsigned int>(x) >> i*8) & 0xFF;
};
// allocate temporary buffer.
auto m = std::make_unique<int[]>(n);
int* b = m.get();
// for each byte in integer (assuming 4-byte int).
for ( size_t i, j = 0; j < 4; j++ ) {
// initialize counter to zero;
size_t h[256] = {}, start;
// histogram.
// count each occurrence of indexed-byte value.
for ( i = 0; i < n; i++ )
h[bmask(a[i], j)]++;
// accumulate.
// generate positional offsets. adjust starting point
// if most significant digit.
start = (j != 3) ? 0 : 128;
for ( i = 1+start; i < 256+start; i++ )
h[i % 256] += h[(i-1) % 256];
// distribute.
// stable reordering of elements. backward to avoid shifting
// the counter array.
for ( i = n; i > 0; i-- )
b[--h[bmask(a[i-1], j)]] = a[i-1];
std::swap(a, b);
}
}