Bitmap Sort – Most Efficient Method To Sort Integers

A bitmap sort is the fastest and most efficient way to sort a limited set of integers.  It was first published by Jon Bentley in the book Programming Pearls.  It works by thinking of a chunk of memory as a set of numbered bits.  Each number to be sorted should be thought of as a bit in that chunk of memory.  So, after all the bits are set, then it is a simple matter to obtain the sorted numbers by starting from the beginning (or the end if reverse order is required) and checking if a bit is set.  If so, then it is moved to the output buffer.  The following code has been tested and performs this task:

public static void BitMapSort(int[] InBuf, int[] OutBuf, int MaxInt)
{
   // This function demonstrates how to efficiently sort an array of numbers.
   // Assumes that each element is >= 0.
   // InBuf holds the numbers to be sorted.
   // OutBuf returns the numbers in sorted order.
   // MaxInt identifies the largest number that can be encountered, which is a limitation
   // to this sort technique.
   //
   int Loop, Val, OutIndex;
   //
   int InBufSize = InBuf.Length;
   // Init the bit array to hold enough bits based upon the biggest int.  Initizlied by default to false.
   BitArray BA = new BitArray(MaxInt + 1);
   // Set the corresponding bit in the bit array to the number in InBuf.
   for (Loop = 0; Loop < InBufSize; Loop++)
   {
      Val = InBuf[Loop];
      BA.Set(Val, true);
   }
   // Get each bit set and move it into OutBuf in sorted order.
   OutIndex = 0;
   for (Loop = 0; Loop <= MaxInt; Loop++)
   {
      if (BA.Get(Loop))
      {
         OutBuf[OutIndex++] = Loop;
      }
   }
}

 

The code to test out this function looks like this:

private void TestBitmapSort()
{
   // This function tests out the bitmap sort function.
   Random RandObj = new Random(12345);
   int[] InBuf = new int[1000];
   int[] OutBuf = new int[1000];
   int MaxInt = 75000;
   int Loop, Val;
   // Init the InBuf with random numbers between 0 and
   BitArray BA = new BitArray(MaxInt + 1);
   for (Loop = 0; Loop < 1000; Loop++)
   {
      // Avoid duplicate numbers.
      for (;;)
      {
        Val = RandObj.Next(MaxInt + 1);
        if (BA.Get(Val))
          continue;
        InBuf[Loop] = Val;
        BA.Set(Val, true);
        break;
      }
   }
   FastEvaluate.BitMapSort(InBuf, OutBuf, MaxInt);
   for (Loop = 0; Loop < 999; Loop++)
   {
      if (OutBuf[Loop] >= OutBuf[Loop+1])
      {
        LogMessage("TestBitmapSort failed");
        break;
      }
   }
}
Advertisements

About Bob Bryan

Software developer for over 20 years. Interested in efficient software methodology, user requirements, design, implementation, and testing. Experienced with C#, WPF, C++ , VB, Sql Server, stored procedures, and office tools. MCSD.
This entry was posted in C#, software design, software development, Sort and tagged . Bookmark the permalink.

4 Responses to Bitmap Sort – Most Efficient Method To Sort Integers

  1. Arun says:

    Hi Bob,
    Is there any way to sort non unique set of numbers using bit map sort

  2. Bob Bryan says:

    Hi Arun,

    Assuming that by non unique set of numbers you mean the possibility of duplicate numbers in the set of numbers to be sorted, then yes there is a way to do that. The duplicates for each number need to be counted. So, the question now becomes – what is the best way to do that. If you are working with small 2-byte integers, then the best way to do this is to simply replace the BitArray with a short or int array – for example:

    short BA = new short(short.MaxValue);

    Then, in the first loop replace:

    BA.Set(Val, true);

    with:

    BA[Val]++;

    But, if you are using 4-byte ints, then this approach would probably use too much memory since it would take something like 8gb for the BA array alone. So, instead of using a bitmap this code would then use an array to count the number of duplicates. The following code has been tested and does this properly, but only works with 2-byte integers:

    public static void BitMapSort(short[] InBuf, short[] OutBuf)
    {
       // This function demonstrates how to efficiently sort an array of numbers.
       // Assumes that each element is >= 0.
       // InBuf holds the numbers to be sorted.
       // OutBuf returns the numbers in sorted order.
       //
       short Loop, Loop1, Val, OutIndex;
       //
       int InBufSize = InBuf.Length;
       // Init the array to keep track of duplicates.
       short[] BA = new short[short.MaxValue];
       // Increment the count for each number in InBuf.
       for (Loop = 0; Loop < InBufSize; Loop++)
       {
          Val = InBuf[Loop];
          BA[Val]++;
       }
       // For each entry in BA > 0, move it into OutBuf in sorted order.
       OutIndex = 0;
       for (Loop = 0; Loop < short.MaxValue; Loop++)
       {
          for (Loop1 = 0; Loop1 < BA[Loop]; Loop1++)
          {
             OutBuf[OutIndex++] = Loop;
          }
       }
    }
    

    To sort 4-byte ints with duplicates, a generic hashtable can be used to keep track of the duplicates. Containers like hashtables and lists should always use the generic version because they are more efficient and provide type safety. The generic container for a hashtable in C# is called a Dictionary and is located in the System.Collections.Generic namespace. The following code can be used to sort 4-byte ints that contain duplicates:

    public static void BitMapSortWithDups(int[] InBuf, int[] OutBuf, int MaxInt)
    {
       // This function demonstrates how to efficiently sort an array of numbers.
       // Assumes that each element is >= 0.
       // InBuf holds the numbers to be sorted.
       // OutBuf returns the numbers in sorted order.
       // MaxInt identifies the largest number that can be encountered, which is a
       // limitation to this sort technique.
       //
       int Loop, Val, OutIndex;
       //
       int InBufSize = InBuf.Length;
    
       // init the hash table used to track duplicates.
       Dictionary<int, int> DupCount = new Dictionary<int, int>();
    
       // Init the bit array to hold enough bits based upon the biggest int.
       BitArray BA = new BitArray(MaxInt + 1);
       // Set the corresponding bit in the bit array to the number in InBuf.
       for (Loop = 0; Loop < InBufSize; Loop++)
       {
          Val = InBuf[Loop];
          BA.Set(Val, true);
          // If this is not the first time we have seen this key,
          // then increment the count for it.
          if (DupCount.ContainsKey(Val))
          {
             DupCount[Val]++;
          }
          // Otherwise this is the first time this key has been encountered.
          // So, initialize the count to zero.
          else
          {
             DupCount.Add(Val, 1);
          }
       }
       // Get each bit set and move it into OutBuf in sorted order.
       int Loop1;
       OutIndex = 0;
       for (Loop = 0; Loop <= MaxInt; Loop++)
       {
          if (BA.Get(Loop))
          {
             // Move all the duplicates to the output array.
             for (Loop1 = 0; Loop1 < DupCount[Loop]; Loop1++)
                OutBuf[OutIndex++] = Loop;
          }
       }
    }
    

    I tried testing the above code and it appears to work as advertised.

  3. Anonymous says:

    anyone know the code to help ease fears with

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s