Insertion Sort in Different Flavors

NOTE: Blog moved to Wordpress. Click here for latest posts and more cool stuffs.

Been revving up algorithms for my job hunt. Thought, I should share some. Here's Insertion Sort, in Ruby, Java and C.

It has a Worst and Average Case Scenario Complexity of Theta(n^2) (or Theta n-squared). It is efficient for smaller data sets while larger data sets would require a lot of time for sorting.

Oh! I've also been dabbling in the art of Ruby Programming.

I find the language a lot more neat and simpler than my previously known languages - C and Java. The best thing is that with multiple syntax possibility, I can quickly code in free flow without the need to frequently check and recheck whetehr I'm sticking to the syntax rules to express my thoughts.

This is one of the features of ruby to have multiple syntax rules for the same task, incorporated from C, Python, Small-Talk, Java and more. This makes it easy to learn and apply.

Without further delay, here's the algorithm;

INSERTION SORT (PSEUDO-CODE)

A = [1,5,3,7,6,2,8,9,10,4]

print "Initial Array Order " + A

for j = 1 to A.length
{
i = j-1
key = A[j]

while i>=0 && A[i]>key
{
A[i+1] = A[i]
i = i-1
}

A[i+1] = key
}

print "Sorted Array Order "+ A

OUTPUT>> [1,2,3,4,5,6,7,8,9,10]

Note: The above algorithm assumes a Zero indexing for the Array. For One indexed Arrays, alter the for loop to -

"for j = 2 to A.length"

and alter the while loop to -

"while i>0 && A[i]>key"

Now, Insertion Sort in Ruby;

INSERTION SORT (RUBY)

A = [1,5,3,7,6,2,8,9,10,4]

p "Initial Array Order"
p A

for j in 1...A.length

i = j-1;
key = A[j];

while i>=0 && A[i]>key

A[i+1] = A[i];
i = i-1;

end

A[i+1] = key;

end

p "Sorted Array Order"
p A

Here's the screen shot of the running Ruby program:

InsertionSort (Java)

public class InsertionSorting
{
public static void main( String[] args )
{

int A[] = { 10, 9, 5, 7, 3, 1 };

System.out.printf("\nInitial Array:\n");

for( int k=0;  k<A.length;  k++)
{
System.out.printf( "%d, ", A[k]);
}

for( int j=1;  j<A.length;  j++)
{
int i = j-1;
int key = A[j];

while((i>=0)&&(A[i]>key))
{
A[i+1] = A[i];
i=i-1;
}

A[i+1] = key;
}

System.out.println("\nFinal Array:");

for( int k=0;  k<A.length;  k++)
{
System.out.printf("%d, ",A[k]);
}
}
}

Here's the screen shot of the running Java program:

Java program run in Netbeans IDE.

INSERTION SORT (C)

//Insertion Sort

void main()
{

int A[6] = { 10, 5, 7, 3, 4, 1 };

printf("\nInitial Array\n");

for ( int l=0;  l<6;  l++)
{
printf("%d\n", A[l]);
}

int j =0;
for( j=1;  j<6;  j++)
{
int i = j-1;
int key = A[j];

while((i>=0)&&(A[i]>key))
{
A[i+1] = A[i];
i=i-1;
}
A[i+1] = key;
}

printf("\nFinal Array\n");

for (int k=0; k<6; k++)
{
printf("%d\n", A[k]);
}

getch();

}

Here's the screen shot of the running C program:

[C Program compiled with TCC.]

Hey! It's a nice idea to code the same stuff in C, Java and Ruby. Next time onward I'll try to post programs in all three languages. Not entire applications, though, it gets tedious when the program runs long.

Next hopefully should be Data Structures Stack and Queue, or Merge Sort. Lets see. Till then, adios!

PS: Attached Ruby, Java and C files. [LINK]