-
Bit-sorting in Java
I've written a fairly simple bit-sort (technically a base 2 radix-sort)
and am looking for suggestions in optimizing. No, this isn't a homework assignment;
and no, it's not for my job, either. I've posted my current revision below.
Any comments (outside the realm of program structure) are welcome.
Thanks in advance.
P.S. Please note that my references to "next most significant bit" assume
little-endian. Thanks again!
public class RadixSort
{
public static void main(String[] args)
{
// Test data - change at will
byte[] baData = {9, 6, 7, 3, 4, 8, 2, 1, 5, 0, 15, 23, 75};
// Array to store 1 results from current radix iteration
byte[] baOnes = new byte[baData.length];
// Array to store 0 results from current radix iteration
byte[] baZeroes = new byte[baData.length];
// Number of elements in saOnes (different from saOnes.length)
int iOneCount = 0;
// Number of elements in saZeroes (different from saZeroes.length)
int iZeroCount = 0;
// Current bit (radix) we're searching against
int iMask = 1;
for (int iBitCount = 0; iBitCount < 8; iBitCount++)
{
iOneCount = 0;
iZeroCount = 0;
for (int iSort = 0; iSort < baData.length; iSort++)
{
if ((baData[iSort] & iMask) != 0)
{
baOnes[iOneCount++] = baData[iSort];
}
else
{
baZeroes[iZeroCount++] = baData[iSort];
}
}
// Append the 0s to the 1s array -- Main area to be optimized
int iLength = baData.length - iOneCount;
for (int i = 0; i < iLength; i++)
baOnes[iOneCount++] = baZeroes[i];
// Put the whole thing into our data array
baData = baOnes;
// Shift our mask to the next most significant bit
iMask <<= 1;
}
}
}
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
Forum Rules
|
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL
|
Bookmarks