Radix sorting algorithm
I have been provided with some algorithms for reverse engineering. The algorithm below is a radix sort, but I am very confused about what is actually going on in the code.
I'm new to algorithms and don't know how the code sorts the elements in an array. I'm not sure which bits are related to the algorithm and what the mask is. Here is the code:
ArrayList<Integer> array = CopyArray(a);
Integer[] zerobucket = new Integer[a.size()];
Integer[] onebucket = new Integer[a.size()];
int i, bit;
Integer element, mask;
for (bit=0; bit<8; ++bit) {
int zc = 0;
int oc = 0;
for(i=0; i<array.size(); ++i) {
element = array.get(i);
mask = 1 << bit;
if ((element & mask) == 0) {
zerobucket[zc++] = array.get(i);
} else {
onebucket[oc++] = array.get(i);
}
}
for(i=0; i<oc; ++i) array.set(i,onebucket[i]);
for(i=0; i<zc; ++i) array.set(i+oc,zerobucket[i]);
}
return(array);
source to share
Algorithms is where you should start learning programming!
To see what the undocumented code snippet does, you may need to use pseudo-language to put this work in an English math operator.
For example, you note that this snippet should only work for 8-bit numbers (outer loop per bit). The rough description is that the elements of the array are "sorted" into two buckets depending on whether the bit in the bit position is zero or one starting from the bit in the significant lease position. The original array is then reordered with "ones" preceding "zeros" .., which should order the array from largest to smallest.
It will work well for you to look for radix sorting algorithms and start from there rather than start from code.
source to share
Your algorithm works for 8 bit numbers and you are looking at one bit at a time. A clearer example is this: using decimal instead of binary.
Sort on 1s: 771 721 822 955 405 5 925 825 777 28 829
Sort on 10s: 405 5 721 822 925 825 28 829 955 771 777
Sort on 100s: 5 28 405 721 771 777 822 825 829 925 955
After sorting by the middle digit, notice that the numbers are sorted by their last two digits. After sorting by the most significant digit, the digits are completely sorted.
The same goes for binary. The number of buckets we use for sorting is SAME, as the base number we use as the sorting key during one bucket or sorting pass. "Radix" is synonymous with base number , hence the name "sort by method". In your example, the number is 2.
source to share
A mask , or bitmask, is used to "turn off" every bit except those that are allowed to "see" through the mask. 0
filter out the bit they AND
ed, 1
allow the bit. A common use is to isolate part of the size of an integer type with a byte:
00000000 11111111 00000000 00000000
& // Boolean AND
10010101 10010101 10010101 10010101
yields
00000000 10010101 00000000 00000000
source to share
/*try this iterative method and 100% working*/
#include<stdio.h>
#include<math.h>
int sort();
int display();
long int a[20],n;
int main(){
int i;
printf("enter the size:");
scanf("%d",&n);
printf("\nenter the array elements\n");
for(i=0;i<n;i++){scanf("%d",&a[i]);}
sort();
return 0;
}
int sort()
{
int p=0,rad[20],q,s=0,i=0;
int k1,k2,t;
while(p<=3)
{
q=0;
while(q<=9)
{
i=0;
while(a[i]!='\0')
{
t=pow(10,(p+1));
k1=a[i]%t;
k2=k1/pow(10,p);
if(k2==q) {rad[s]=a[i];s++;}
i++;
}
q++;
}
s=0;
printf("\n sort for %dth\n",p);
for(i=0;i<n;i++){a[i]=rad[i];}
printf("\n");
display();
p++;
}
return 0;
}
int display(){
int i=0;
while(a[i]!='\0')
{
printf("%d\t",a[i]);
i++;
}
return 0;
}
source to share