Merging Multiple Arrays of equal size using LINQ

Merging arrays or collections implementing IEnumerable  can be  useful at times.

For example,consider two integer arrays of equal length .

int[] numArrOne = new int[] { 1, 2, 3, 4 };
int[] numArrTwo = new int[] { 5, 6, 7, 8 };

LINQ's zip can be used to merge them(the elements are added(merged) along their indices)
 

mergedNumbers will  now have the new elements   { 6, 8, 10, 12 }

But what if we want to merge Multiple Arrays and not just two? The Zip method only works with two sequences and not more than that.Ok so is there a way around?.Yes when you combine Aggregate and Zip together, you have what you need.

But first off you need to store all of the arrays on a single List

int[] numArrOne = new int[] { 1, 2, 3, 4 };
int[] numArrTwo = new int[] { 5, 6, 7, 8 };
int[] numArrThree = new int[] { 5, 6, 7, 8 }; 

List<int[]> numberStore = new List<int[]>() { numArrOne, numArrTwo, numArrThree };

LINQ

mergedNumbers will now have 11,14,17,20 after merging all three arrays.

This LINQ will merge any number of Arrays and will produce a single array.

The word Merging is quite broad and can take different meanings,depending on the type of elements you have in the collection.If you are running this same operation on arrays of strings,it is going to give a different meaning to the output.


CodeIgnoto

Writing a Square Root function from scratch

• How it works?
• C#
• Python

Most of the modern programming languages we use today have built in libraries to handle mathematical functions.Every language ships with a rich math library that can easily handle most of the mathematical tasks.Finding square root is one. Calculating square roots is so prevalent,that most of us have the square roots memorized up to certain extent.System.Math.Sqrt() is the .Net's answer to this widely used function.It takes a double datatype as a single parameter and returns the square root(as double).Well before programming languages it was the handheld calculators that made this function a household among users.In all my years i have never manually calculated the square root of any number until  recently i read about a method called Newton-Raphson's method.There are few other methods like the Babylonian and indian bakshali approximation,which i suggest to have a look at.

How it works?

To find the square root of a Given Number N

   Maintain a variable called G,with a initial value of 1.//G=1;

   Maintain a variable called Q

   Maintain a variable called AVG

STEP 1: Divide N by G  (N/G) and store the result in a variable  Q

STEP 2: Calculate the Average of Q and G and store in AVG

STEP 3: Check if AVG = = G

                  If AVG != G 

                      Assign the value of AVG to G and repeat STEP 1 through 3

                  If AVG == G

                      Exit as Square root found.(Current value in AVG and G is the square root)

Complete Iteration for getting the square root of 9

G=1  ;  N=9   ;  Square root = 3

On the last row both the variable G's value and the Average(step 2) equals and that is where you get your square root.So when your value stored in G equals the Average calculated you can stop and come out.

How it works?

using System;
namespace SquareRoot
{
    class Program
    {
        static double inputNumber;
        static double guess = 1;
        static double quotient = 0;
        static double avg = 0;
        static bool exit = false;

        static void Main(string[] args)
        {
            Console.WriteLine("Please enter the number:");
            if (double.TryParse(Console.ReadLine(), out inputNumber))
            {
                while (!exit)
                {
                    quotient = inputNumber / guess;
                    avg = (guess + quotient) / 2;
                    if (avg == guess)
                        exit = true;
                    else
                        guess = avg;
                }
                Console.WriteLine("The Square root of " 
                                  + inputNumber + " is: " +guess);
            }
            else
                Console.WriteLine("Your input doesn't seem to be numeric");

            
            Console.ReadLine();
            
        }
    }
}

A short implementation of the same in python.

number=float(169)
guess=float(1)
exitLoop=False

while not exitLoop:
    quot=number/guess
    avg=(guess+quot)/2
    if avg == guess:
        exitLoop=True
    else:
        guess=avg
        
print("Square root {0} is {1}.".format(number,guess))

Project Euler - Problem 98

• Problem 98
• Solution
• Console output

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36². What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96². We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

First of all we need to find out all anagrams in the given file.For the few of you who may think what is an anagram.Anagram is a word, phrase, or name formed by rearranging the letters of another word.A Simple example of that are the words ITEM and TIME.Both of the words have same set of characters,but give different meanings when rearranged.The following piece of LINQ gets all anagrams in the file.

var anagrams_1=textContent.Split(',')
                          .Select(str => new CustomString(str));
var anagrams =  anagrams_1.GroupBy(cstr => cstr.sortedString)
                            .Where(g => g.Count() > 1)
                            .Select(g => g.Key);

textContent is a string datatype housing the entire textual content pulled off from word.txt file.The CustomString struct is created for every word in the file and it stores two different states.Sorted String state and the  Original string.A sorted string will have its letters sorted left to right in a alphabetical order.The unsorted string will maintain its original arrangement of letters.In the case of words TIME and ITEM ,the sorted and unsorted original state would look like below.

          CustomString for TIME : Sorted String : EIMT, Original String: TIME

          CustomString for ITEM : Sorted String : EIMT, Original String: ITEM

       

          If we compare the Sorted string(EIMT)of both the words we can conclude quickly that these

          two are anagrams.

struct CustomString {

 public char[] charArrayOrg;
 public char[] sortedCharArr;
 public string sortedString;
 public string originalString;

 public CustomString(String source) {

   charArrayOrg = source.ToCharArray();
   sortedCharArr = source.ToCharArray();
   Array.Sort(sortedCharArr);
   sortedString = new String(sortedCharArr);
   originalString = new String(charArrayOrg);

}}

The extension method Select() takes every string and transforms it to a CustomString object.Then all the objects are grouped by its SortedString state.Each group in the LINQ result set will correspond to a unique anagram from the word.txt file.

Next we need to generate all possible square numbers that match the length of every anagram word(Brute Force). And we need to positionally apply each of the digits to every character in the word starting from left to right.
Lets take the anagrams TIME and ITEM(both 4 letters) to get the explanation straight.Our squares should match the length of the anagrams,in this case we will consider 1225(4 digits) which is the square of 35.

                                    1  2  2   5

                                    T  I  M  E

In the next step we rearrange the letters to form its anagram ITEM.As we rearrange the numbers get shuffled as you can see below.

                                   2  1   5  2

                                   I   T  E  M 


ForEach loop for Rearranging the letters.

    
foreach (char ch in match.originalString)
{
    bool elePlaced = false;
    while (!elePlaced)
    {
        var idx = ele.originalString.IndexOf(ch, startSearchAt);
        if (shufflerList[idx] == '\0')
        {
            shufflerList.RemoveAt(idx);
            shufflerList.Insert(idx,    
                        sqrSeedString[match.originalString.IndexOf(ch)]);
            elePlaced = true;
        }
        else
            startSearchAt = idx + 1;
    }
    startSearchAt = 0;
}

Lastly we need to check whether the newly formed number is a square or not.2152 is not a square number.

Project Euler Problem 57

Problem 57

Solved a simple problem from Euler again.You can have a look at the problem statement below.

Problem statement:

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5

1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Approach:

If you look at the fractional progressions below(same given on the question as well),you will find that there is a clear arithmetical pattern to it.

3/2 , 7/5 , 17/12 , 41/29

you can clearly see that the denominator on every fraction is the summing of both nominator and denominator of the previous fraction.

for (e.g) take the fraction 3/2

3 (nom) / 2 (denom) => 3+2 = 5 (which is the denom for the next fraction 7/5)

similarly  for the next fraction 7/5

7+5= 12 (which is the denominator for the next fraction 17/12)

You will also see that the numerator on every successive fraction is the sum of previous fraction's numerator and the corresponding denominator multiplied with 2.

Lets take the first fraction on our list again which is 3/2

Numerator=3

Denominator=2

Next Numerator = (denominator x 2) + numerator

           7             =         (2 x 2)          +      3

as we have seen already the new denominator for the next fraction,would be Numerator + denominator of previous fraction(3/2)

3+2=5.

and we get the next fraction as 7/5

So to reiterate again the formula that is used to calculate the next fractions.

Next Denominator= Current Numerator + Current Denominator

Next numerator = Current Numerator+(Current Denominator X 2)

C# Code

C# with its primitive data type cannot really handle the kind of number crunching that is required for this program.As you will see the numbers can get really big before the program can complete.The basic reason is c# never was designed to do such calculations in the first place.But still framework in its release 4.5 has introduced a new datatype called BigInteger that saves the day for this challenge.BigInteger "Represents an arbitrarily large signed integer."-MSDN

This Euler challenge was basically to generate all fractions up to 1000 times and then see out of all those fractions,how many of them have their numerator's digit count greater than the denomintor's digit count.

Here is the code.Download

Not sharing my output as it would be a spoiler. Still what i would like to share is the numerator part of the fraction that got generated on the 1000th iteration.

72016336943533875056131468444247239328723197628440751797201898063588088312700201943482948477109536203740206649612702729920170001354454107173480483962605519493117789821758457767858986227019805650639002566946496865364666543562826303377877700877266135276209125278037204443042487153089226849544681245300260167141025277156482737568934079466850318276966893735585103845471745828701580706481

Yes that's a number and thanks to BigInteger :)

happy coding !!!
Polybius

Click here for other Topics

Contents at a Glance

1. Radix Sort - Part-I
2. Radix Sort - Part-II
3. Run length encoding
4. Sieve of Eratosthenes
5. Pascal's Triangle
6. Project Euler Problem 112 - Bouncing Numbers
7. Ulam Spiral
8. Project Euler Problem 57 
9. Project Euler Problem 98

Ulam Spiral

• How it works?
• C# Code

Prime spiral

Ulam spiral is a mathematical structure where numbers are written in a spiral form starting from 1.It is said that this spiral came into existence during a boring meeting,which Ulam was attending.During the meet he got bored and started doodling on his paper a number spiral with 1 at the center and the next numbers following it in a spiral fashion.What surprised Ulam was not the spiral but the placements of the prime numbers on the spiral.As you can see in the second image(right),the prime numbers have aligned themselves in a diagonal fashion.The Ulam spiral is used for understanding the tendencies and behaviors of prime numbers.This post will show you how to generate Ulam spirals and in my next post i will use it to solve a Project Euler problem.

A Ulam spiral on the left and the right spiral with prime numbers marked
courtesy wiki

The above image is a matrix of dimension 7 x 7 with N 49.

Lets take a small matrix of dimension 4 x 4 and see how we can work out.(Max number :16)

A 4 x 4 Matrix with two cycles( Cycle 1- Gray,Cycle 2 -Red) 

Since matrix is a four sided representation every cycle will have 4 iterations(top,left,bottom,right).The gray and red marks in the above image represents two different cycles.

A cycle will be deemed complete when all the cells for that cycle is filled.To work out the number of cells per cycle do (dimension -1) * 4

if we apply this for both the cycles we get

Cycle 1    4-1 * 4 =12

Cycle 2    2-1 * 4= 4 (dimension of red block is 2)

So we have a total of 16 cells to fill ,with 12 cells to fill in cycle 1 and 4 cells to complete in cycle 2.

We will start filling the numbers from the top right corner of matrix,moving left with the placement of every number and cycle in a anticlockwise movement filling all the four sides of every cycle.

By changing the row index and column index of our array ,we can easily move in the direction we want.The direction information will be stored in a small array which would instruct the program to go in a certain direction.{E,S,W,N} E- East,S-South,W-West,N-North.

On first iteration of cycle 1 we would move East and during the second iteration Move South.

On third move West and on the final iteration move North(which is what the direction array {E,S,W,N} tells that in a programmatic fashion) .But how do we know when to stop and change the direction.Simple ,stop after filling (dimension -1) cells on every iteration,then move by one cell in the direction you were moving.Finally change the direction with the help of direction array.

So in our example we need to fill (4-1)=3 cells in every iteration of Cycle 1

For the second cycle we need to fill just one cell on every side.as(2-1)=1

The same procedure will have to be repeated on every cycle until all the cells are filled.

There is one more question to answer how would you move from one cycle to other(gray to red) inside of a matrix.Its simple again subtract your current cycle's dimension by 2 you get the dimension of the enclosed matrix.

for e.g 
Cycle 1 dimension  = 4 
Cycle 2 dimentsion =Cycle 1 dimension  - 2 =  2 (refer second image for clarity).

C# Code

Download Code

Console Output

Ulam spiral for 10 x 10 Matrix

Project Euler Problem 112 - Bouncing Numbers

Problem statement from ProjectEuler.net

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy.

In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Solution in C#

Console output :

Console output generating bouncy numbers

Click here for other Topics

Pascal's Triangle

 Download Code

Pascal triangle is a well known mathematical structure formed out of numbers.To be specific this structure is triangular in shape.The structure was invented by a french mathematician Blaise Pascal.Various patterns on this triangle gives out to triangular numbers,polygonal numbers,squared, Fibonacci and can be used for binomial expansions.

A simple pascal triangle with 6 rows look like below

pascal triangle

The numbers will be have to be generated in rows.

On the first row just place 1 and both its left hand side and right hand side is occupied by zeroes,though not showed in the above image.Every row in the triangle should have it's starting and ending number as zero.so our first row will be exactly like below.

0    1     0

to generate the numbers on the second row

   1.  write down the first zero from row 1 as it is. 0

  =  1

 2.  next from the first row,add the first number with second number 

               =  1

 3.  and then add the second number with the third number 

   4.  Finally write down the last zero as it is which gives us the numbers for the second row as below                                                                                          

                                      

   5.  for generating the third row,we will have to execute the same steps that we followed earlier.

                                    
                                     
                                     
        which would result in following numbers for row 3.
        0   1   2   1  0.

You can keep repeating this and generate as many rows you want in your triangle.

C# Implementation

Here goes the C# Implementation.

Console Output

Console window generating the Pascal triangle for 10 rows

Click here for other Topics

Sieve of Eratosthenes

• The Sieve
• C# Code
• Console output

Prime numbers are notably the most discussed and revered topic in mathematics. And rightly so we can find its application in myriad of fields. So what is a prime number?.Any number that is divisible by 1 and itself is a prime number(2,3,5,7.....).Prime number's appliance is far reaching and its application can be found on number theory,encryption to name a few. Here is the wiki link on Prime Numbers that gives an exhaustive information.

For centuries prime numbers captivated the minds of mathematicians. A Greek mathematician named Euclid asserted that ,there are "infinitely many prime numbers".Over the centuries, many mathetimatcians invented ways to extract prime numbers upto a given number N.The process of extracting all the prime numbers up to a given number n is formally termed as "SIEVING".One of the earliest form of sieving was invented by a mathematician named Eratosthenes.A Polymath from Greece and the  first man to calculate the circumference of earth. Let us look at the simple method advised by Eratosthenes to extract all the primes up to a Number N.

Lets say to extract all primes up to 20 (N)

Write down all the numbers from 2 to 20 (1 is not a prime number so u have to exclude them everywhere)

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

First number in the List is  2;strike out every 2nd number in the list after it(all multiples of 2).

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next on the list after 2 is 3;now cross out every 3rd number on the list(all multiples of 3).

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next on list is 5;cross out every 5th number.A number could have been crossed out on a previous iteration ,which should not be a problem.As you can see below 10 was striked on the first iteration itself and would also be a candidate for 5.

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next is 7
2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20.(no changes to the list)

Next is 11.
Now you can stop as 11+11 =22 which is greater than your Max number N (20).So no use in proceeding further and can stop.

Now if we read out all the numbers that are not striked,we get the primes.

2  3  5  7  11  13  17  19

C# Implementation

I am using an array to initialize and strike out the numbers.
A StopWatch class to see how much time the program takes to complete the sieving.
A Parallel class to improve the performance a bit.

The following code can sieve only up to  100 Million numbers(100000000).This is due to the fact that ,the array size is limited by system's virtual memory.I am running a AMD A8 4500 with 4GB RAM and this is the max i can go up to.We can still notch up the higher limit by replacing array with a List<T>.But i am not taking that route right now,may be ill improvise on this in future.

Without further ado,here goes the code.

namespace EratosthenesPrimeSieve
{
class Program
{
static int[] numbers = new int[100000000];
static int maxNumber;

static void Main(string[] args)
{
    Console.WriteLine("Please enter a max number ");
    maxNumber = int.Parse(Console.ReadLine());
    Stopwatch sw = new Stopwatch();

    sw.Start();
    for (int num = 2; num < maxNumber + 1; num++)
        numbers[num - 2] = num;
    sw.Stop();
    Console.WriteLine("Array fill complete. Time elapsed :" +
        (double)sw.ElapsedMilliseconds / 1000);

    sw.Restart();
    for (int idx = 0; idx < maxNumber - 3; idx++)
    {
        int num = numbers[idx];
        if (num != 0)
        {
            while (num + idx < maxNumber)
            {
                numbers[idx + num] = '\0';
                num += numbers[idx];
            }
        }
    }
    sw.Stop();
    Console.WriteLine("Removed all non primes from the array. Time elapsed :" +
                        (double)sw.ElapsedMilliseconds / 1000 + "\n" +
                        "Press enter to display all the primes upto " + maxNumber);

    IEnumerable result = numbers.Where(num => num != 0);
    Console.WriteLine("Primes found :" + result.Count());
    Console.ReadLine();
    Parallel.ForEach(result, p => Console.Write(p + ","));

    Console.ReadLine();

}
}
}

Run length encoding

• The Encoding
• C# Code

Compression makes data lighter and at the same time occupy less disk space.on this post i will be talking about a widely used algorithm called "Run Length Encoding".The algorithm itself is easy to understand and can be implemented in a very terse way.The Algorithm is best suited for compressing images.Wiki gives us a fair amount of information about its origin and its applications in the past.

what is Run length encoding?

Imagine you have some random data with you that look like below.

RRRRREEEDDISSSSBBBBLLAAACCCKK.

If i count all the characters starting from left to right ,i have a total of  28 characters in it(not a big sized data,but will keep that way for the sake of simplicity).So how do we compress such data or how do we represent the data in  a much shorter form without losing its meaning.

Run length Encoding tells us "If you have multiple occurrences of a character/element in the data,just keep one instance of that character and specify how many times it has appeared on the data".As you can see this can greatly reduce the duplicates.

Taking the previous thought into consideration we will end up with a shorter form of the same data(without losing its meaning) as below.

R5 E3 D2 I1 S4 B4 L2 A3 C3 K2

we had R appear 5 times,E 3 times,D 2 times I 1 time,S 4 times and so on.

One important thing to note is ,if a character reappear on the data with a different character(s) in between them.you will have to start recounting the occurences again.

for e.g compressing

BBOBBB becomes B2O1B3

Deflating or decompressing is very simple as you have to just represent a char ,the times being specified.

B2 --> BB
O3 --> OOO.

More examples can be found on the wikipedia  page.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace RunLengthEncoder
{
class Program
{
    char[] dataArray;
    public void Run(String input)
    {
    int repititons = 0;
    int charIndex = 0;
    dataArray = input.ToCharArray();
    StringBuilder compressedData = new StringBuilder();

    while (charIndex < dataArray.Length)
    {
        var ch = dataArray[charIndex];
        while (charIndex < dataArray.Length 
               && !(ch != dataArray[charIndex]))
        {
            ch = dataArray[charIndex];
            repititons += 1;
            charIndex += 1;
        }
        compressedData.Append(repititons);
        compressedData.Append(ch);
        repititons = 0;
    }
    Console.WriteLine("Compressed data " + compressedData.ToString());
    Console.ReadLine();
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Please enter some data");
        var input = Console.ReadLine();
        Program p = new Program();
        p.Run(input);
    }
}
}

Radix Sort -Part II

In our previous post we looked at the fundamentals of Radix sorting .
we also ran few examples to see the algorithm at work.On today's post we will be looking at the low level implementation of this sorting mechanism.

Click here for PART -I  Fundamentals

What we need to do is to single out a digit from every number (could be a single digit) and then decide which bucket it belongs. The Algorithm makes an assumption that the bucket number cannot exceed number 9 (0<= buketNumber < 10). The most important player in the scheme of things is the modulo operator (%).

Before we dig in we need to look at what lsd's and msd's are.Could be trivial for most but is crucial.

What is an LSD and MSD?

They are least significant digit and most significant digit. In our example

LSD OF 435 is 5

MSD OF 435 is 4.

My algorithm starts from LSD although you can start from MSD and move towards right.

For a number 435 how do we move from left to right?

We do 435 % 10 = 5 so we place the number in bucket 5.

Now to move left on the next iteration you multiply the divider by 10.

435 %( 10* 10) = 435%100= 35

What we have got here is a 2 digit number (35) with one digit (5) already processed so we need to get rid 5 from it. To get rid you do below.

(35 – (35 %10))/10

35 -5 /10

30/10

3 (so you know you need to place the number in bucket 3)

Now in the next iteration,the divider is again multiplied with 10 to get below

435 % (10*10*10) =435%1000=435.

What we need is the leftmost digit 4 from 435.so we keep repeating the steps that we did earlier 

(435 – (435%10))/10 = 430/10= 43

(43-(43%10))/10=40/10 = 4

Finally we know we need to place the number in Bucket 4.

C# Implementation

       

       The sort method does all the hard work.

       Output

     Here is the complete working code :)

Cheers

POLYBIUS

Click here for other Topics

Radix Sort

Radix Sort - I

How it Works

Radix sort is one of the various sorting algorithms which is prevalently used to sort data.The algorithm is fairly simple and can be implemented on any language quite easily.In this post we will look at how to sort a set of numerical data and the program to achieve that would be in C#.

Lets say you want to sort the following numbers in sequential order using Radix

23  12  45   67  34

Radix sort employs a very simple way of looking at the unit of every element and then subsequently placing the element in a bucket that corresponds to the unit.What i mean is 

for a given number 43 i am suggesting here 4 and 3 are the 2 units that make up the whole number.so when you are looking at unit 4 the number 43 would belong to bucket 4 and for 3 it would be bucket 3.All this would be clear with a following example.

we will always start with the least significant digit(of every numeric element in this case) and gradually move towards left on every iteration.The numbers marked below are the least significant digits.we also maintain a bucket for every digit 0 - 9.

 23  12  45  13  67  34

After pass one our buckets and its containing elements will look like below. 

if we read out elements in the buckets 0 -9 we get the new sequence(may or may not be sorted).

12   23   13   34  45   67

Now we need to sort  this list again based on the next unit (move towards left).

12   23   13   34  45   67

After this second pass our Buckets  will look like below.

Now if we read out the elements we can see the elements are sorted

12   13   23   34   45   67

so to sort this list we needed two pass.But this may not be the case when you have mix of elements whose number of digits are different.we will see how we are handling this in second part where i also show the program written in C#.

More details on this algorithm can be found on this  page

Continue to Part -II (C# Implementation)

Click here for other Topics