Simple Algorithms
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<size; i++)
{
int j;
for(j=i+1 ;j<size; j++)
{
if(a[i]>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<size-1;i++)
{
p(a,size);
if(a[i]>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] > 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
}
}
}
Permalink: simple-algorithms
Tags: bubble sort