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