Algorithms, C#

Let us QuickSort in C#

I must agree that QuickSort was one of the first Algorithms I staggered and stumbled upon.

It still mesmerizes me on how Mr. Hoare came up with clever, yet so simple way to sort elements.

It has been a while I have written a sorting algorithm, mostly because of the fact I happen to code in C# and sorting and searching is one among various algorithms we take for granted.

So I tried to code it in C# and here it goes:

 

public static class QuickSorter
   {
       public static void QuickSort(int[] array, int left, int right)
       {
           if (left < right)
           {
               int q = Partition(array, left, right);
               QuickSort(array, left, q - 1);
               QuickSort(array, q + 1, right);
           }
       }
 
       private static int Partition(int[] array, int left, int right)
       {
           int pivot = array[right];
           int i = left-1;
 
           for (int j = left; j < right; j++)
           {
               if (array[j] <= pivot)
               {
                   i++;
                   int temp = array[i];
                   array[i] = array[j];
                   array[j] = temp;
               }
 
           }
 
           int temp1 = array[right];
           array[right] = array[i+1];
           array[i+1] = temp1;
 
           return i + 1;
       }
   }

Final words

Sorting algorithms come in various flavors and each one has a reason and use case to exist.

In fact the Array.Sort method that we often use in C# internally uses Insertion sort/Quick Sort/ Heap sort depending on the input and in case you were to do a stable sort, Array.Sort may not be the right fit for you.

Whenever in doubt I always refer the Sorting Algorithm comparison chart on Wikipedia.

I will follow up with more sorting algorithms and will see when and why to use it.

Advertisements
Standard
Algorithms, C#, Uncategorized

Bit manipulation to the rescue in C#. Reducing Space/Time complexity using Bit Manipulation

Why

Bit manipulation is fun and still  relevant in the realm of C#. You can do things in a way that can increase performance substantially or simplify an algorithm in hand.

Bit manipulation also in certain scenarios helps to save memory, take for example if you want to store multiple flags (True/False values) the most obvious solution would be to use a list of bool types. This may seem to be OK but takes 1 byte per flag. If you are working with 30 flags in hand, you can use an Int32 type in .Net and use its bit values to store 1 for truthy values and 0 for falsy values (often referred as using  bits of an Integer to represent a Set)

So although it’s not imperative to know Bit Manipulation but it can really come to rescue in some corner cases as we plan to see in this blog post.

 

Bitwise Operators

Before diving deep into scenarios where Bit manipulation can come to rescue let’s look into various Bitwise operators so that we all start on the same page:

 NOTE: I am using 8 bits to explain the concepts.

The .Net int type is a  32 bit integer, but the concepts would remain the same 

Bitwise Compliment
/*Bitwise Compliment
             * 1  = 00000001
             * ~1 = 11111110 (In 2's compliment representation this is -2) 
             * ------Explanation of -2:---------
             *  2 = 00000010
             * -2 = 11111101 +1 = 11111110
             */
            Console.WriteLine(~1);
 
 
Bitwise And / Set Intersection

            /*Bitwise And 
             * 1  = 00000001
             * 2  = 00000010
             * 1&2= 00000000 = 0
             */
            Console.WriteLine(1 & 2);
 
Bitwise Or / Set Union
 
            //Bitwise Or
            //1  = 00000001
            //2  = 00000010
            //1|2= 00000011 = 3
            Console.WriteLine(1 | 2);
 
 
Bitwise XOR
            /*
               Here's how XOR works:
             * If both operands have a bit set i.e. 1, the result does not 
             * have that bit set.
             * If neither has a bit set, the result still does not have
             * the bit set. 
             * But if one has the bit set, the result is set.
             * XOR is used for checking bit parity
             */
 
 
            //Bitwise XOR
            //1  = 00000001
            //2  = 00000010
            //1&2= 00000011 = 3
            Console.WriteLine(1 ^ 2);
 
Bitwise Shift Operators
One common use of shifting is to access a particular bit, for example, 
1 << a is a binary number with bit a set and the others clear(bits are 
always counted from the least significant bit, which is numbered 0)
 
Bitwise Right Shift

            //Bitwise Right Shift. Right shift is equivalent to division by 2
            //1   = 00000001
            //1>>2= 00000000 = 0
            Console.WriteLine(1 >> 2);
 
Bitwise Left Shift
 
            //Bitwise Left Shift . Left shift is equivalent to multiplying by 2
            //1   = 00000001
            //1<<2= 00000100 = 4
            Console.WriteLine(1 << 2);
 
Flag Enums
 
            // Bitwise OR operator is used for adding a flag to the Enum
            States states = States.AL | States.TN;
 
            CheckStates(states);
 
            states |= States.MN;
 
            CheckStates(states);
 
            states |= States.WI;
 
            CheckStates(states);
 
            // Bitwise ^ operator is used for removing a flag from the Enum
            states ^= States.AL;
 
            CheckStates(states);
        }
 
         private static void CheckStates(States states)
        {
            switch (states)
            {
 
                case States.AL:
                    {
                        Console.WriteLine("AL");
 
                    }
                    break;
                case States.AL | States.TN:
                    {
                        Console.WriteLine("AL, TN");
 
                    }
                    break;
 
                case States.AL | States.MN:
                    {
                        Console.WriteLine("AL, MN");
 
                    }
                    break;
            }
        }

Set Subtraction

// Set Subtraction
Console.WriteLine(a & ~b);

Set subtraction can be easily understood by using a diagram:

Set Subtraction

Set Subtraction

 

Set Negation

// Set Negation
           Console.WriteLine(ALLBITS ^ a);

Here ALLBITS is an integer value, wherein all bits are 1

 

Set Bit

In order to set a bit, use the following:

// Set Bit
            a |= 1 << shift;

Clear Bit

// Clear Bit
           a &= ~(1 << shift);

 

Now let us look into a few problems wherein we can

leverage Bit manipulations to Reduce Complexity of

an Algorithm/ Reduce space requirements of a program.

 

Scenario 1: Reducing Time Complexity

Given two Integers, find whether they are of opposite signs or not.

Here is the obvious solution:

 

public static bool AreIntegersOfOppositeSigns(int a, int b)
       {
           if (a > 0 && b < 0)
           {
               return true;
           }
 
           if (a < 0 && b > 0)
           {
               return true;
           }
 
           return false;
       }

And here is the solution which uses Bit manipulation:

public static bool AreIntegersOfOppositeSignsUsingBitManipulation(int a, int b)
       {
           return (a^b) < 0;
       }

Did you notice the no. Of lines getting reduced? But it’s not just the lines getting reduced, it’s the complexity/

branching which got reduced here.

First solution has 3 branches/paths and 9 operators whereas the 2nd solution has no branching, additionally just 3 operators.

 

Scenario 2: Reducing Space Complexity

Given a String, determine if all of its characters are Unique

Here is one of the solutions wherein we use a Char Array of size 256 (assuming dealing with ASCII) as a HashTable

to figure out if there are any duplicates:

 

public static bool AreUniqueChars(String str)
     {
         var chars = new bool[256];
         for (int i = 0; i < str.Length; i++)
         {
             int val = str[i];
             if (chars[val]) return false;
             chars[val] = true;
         }
         return true;
     }


public static bool AreUniqueCharsUsingBitManipulation(String str)
   {
       int checker = 0;
       for (int i = 0; i < str.Length; ++i)
       {
           int val = str[i] - 'a';
           if ((checker & (1 << val)) > 0) return false;
           checker |= (1 << val);
       }
       return true;
   }

In this scenario we got rid of the Character array that we were using as a HashTable to detect duplicates.

Final Words

We saw two specific scenarios to reduce Space and Time complexity of an Algorithm. I hope you got the idea of the

power of Bit Manipulation and how can we use it to write performant and efficient code.

Standard
Algorithms

How to find if Two Strings are Anagrams of each other in C#?

In case you are not aware, Anagrams are strings whose characters are some permutation of each other.

For ex: cat, act, tac are anagrams as they are all permutations of ‘a’, ‘c’ and ‘t’.

Here’s the code which checks for the same:

public static bool AreTwoStringsAnagrams(string s1, string s2)
        {
            // Short circuit if any of the strings are null or whitespace 
            if (string.IsNullOrWhiteSpace(s1) || string.IsNullOrWhiteSpace(s2))
            {
                return false;
            }
 
            // Short circuit if the strings are not of equal length
            if (s1.Length != s2.Length)
            {
                return false;
            }
 
            // O(L) space complexity, where L is the Lenght of the largest string
            char[] c1 = s1.ToLower().ToCharArray();
            char[] c2 = s2.ToLower().ToCharArray();
 
            Array.Sort(c1);
            Array.Sort(c2);
 
            for(int i = 0; i < c1.Length; i++)
            {
                if (c1[i] != c2[i])
                {
                    return false;
                }
            }
 
            return true;
        }
Standard