Simple Algorithms

Alex Egg,

For the purposes of science I will implment various algorithms in: C/C++/ruby/python/erlang/go.

Bubble Sort

C Language (Version 1)

I wrote this before looking at any example code.

void bubble_sort_1(int *a, int size)
{
int i;

for(i=0; i&lt;size; i++)
{
int j;
for(j=i+1 ;j&lt;size; j++)
{
if(a[i]&gt;a[j])
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
continue;
}
}
}
}


C Language (Version 2)

However, it seems most other code examples use an infinte outside loop - so I rewrote it.

void bubble_sort_2(int *a, int size)
{
int i;
int swapped;

do
{
swapped=0;
for(i=0;i&lt;size-1;i++)
{
p(a,size);

if(a[i]&gt;a[i+1])
{
int left=a[i];
a[i]=a[i+1];
a[i+1]=left;
swapped=1;
}
}

} while (swapped);
}


Ruby Language

Just cloned it from the C version 2.  Ruby doesn't have a traditioal for loop but has bunch of other itterators in the Array and Enumerable class. The first thing that came to my mind was upto. Although, I'm not sure why it has to be -2 and not -1 like the C example. The swap logic in the ruby sample is a lot nicer – can do it in one line and it makes more sense to look at.

def bubble_sort!(list)
loop  do
swapped=false
0.upto(list.length-2) do |i|
if(list[i]>list[i+1])
list[i], list[i+1] = list[i+1], list[i]
swapped=true
end
end
break unless swapped
end
list
end


Python Language

The phython implimentation follows the ruby version 2 convention needing a -2 on the loop - still not sure why the C version needs -1. If I put a -2 on the C version it has some type of overflow error. I appreciate the python syntax allowing the inline variable swap.

def bubble_sort(list):
#sorting action
swapped=True

while swapped==True:
swapped=False
for i in range(0, len(list)-1):
if list[i] &gt; list[i+1]:
list[i], list[i+1] = list[i+1], list[i]
swapped=True


Go Language

go is good

	for swapped {
swapped = false

for i := 0; i < len(list)-1; i++ {
if list[i] > list[i+1] {
list[i], list[i+1] = list[i+1], list[i] // this is cool -C doesn't have inplace swap
swapped=true
}
}
}