One of the first things I was taught was how to sort an array. Most modern languages have functions to do this for you but it’s still worth knowing the basics behind how. You would be surprised the number of times the same principles are used to perform other operations. Below is my Bubble sort written in Javascript.

A bubble sort works by accending the array and comparing the value at your current location “O(n)” with the value in the next location “O(n+1)”. If the value in the next location is less than the value of your current location “O(n+1) < O(n)” then the two values are swapped “O(n+1) = O(n) and visa versa”.

You can expand on the bubble sort further by running comparisons both accending and descending at the same time, this is known as a double bubble sort. The descending sort has to compare the current position with the one before “O(n-1) > O(n)”, if true the positions are swapped.

function bubbleSort( arrayToSort )
{

  do
  {

    changed=false;

    // loop through the array
    for( i=0;i<(arrayToSort.length-1);i++)
	{

	  // if the O(n) > O(n+1) move O(n) to O(n+1) and O(n+1) to O(n)
	  if ( arrayToSort[i] > arrayToSort[i+1] )
	  {

	    current=arrayToSort[i+1];	  

	    arrayToSort[i+1]=arrayToSort[i];
		arrayToSort[i]=current;

	    changed=true;

	  }

	}

  }
  while( changed==true );
  // break out of loop if no changes are made.

  return arrayToSort;

}

Click the buttons below to see the sort in progress

Run
Reset

Filed under: Programming — Tags: bubble sort, javascript, sorting — admin @ 7:29 pm

After reading an article by Howard Yeend (Pure Mango) I decided I would try to write a version of the basic learn algorithm.

Below is what I came up with.

function kmeans( arrayToProcess, Clusters )
{

  var Groups = new Array();
  var Centroids = new Array();
  var oldCentroids = new Array();
  var changed = false;

  // initialise group arrays
  for( initGroups=0; initGroups < Clusters; initGroups++ )
  {

    Groups[initGroups] = new Array();

  }  

  // pick initial centroids

  initialCentroids=Math.round( arrayToProcess.length/(Clusters+1) );  

  for( i=0; i < Clusters; i++ )
  {

    Centroids[i]=arrayToProcess[ (initialCentroids*(i+1)) ];

  }

  do
  {

    for( j=0; j < Clusters; j++ )
	{

	  Groups[j] = [];

	}

    changed=false;

	for( i=0; i < arrayToProcess.length; i++ )
	{

	  Distance=-1;
	  oldDistance=-1

 	  for( j=0; j < Clusters; j++ )
	  {

        distance = Math.abs( Centroids[j]-arrayToProcess[i] );	

		if ( oldDistance==-1 )
		{

		   oldDistance = distance;
		   newGroup = j;

		}
		else if ( distance <= oldDistance )
		{

		    newGroup=j;
			oldDistance = distance;

		}

	  }	

	  Groups[newGroup].push( arrayToProcess[i] );	  

	}

    oldCentroids=Centroids;

    for ( j=0; j < Clusters; j++ )
	{

      total=0;
	  newCentroid=0;

	  for( i=0; i < Groups[j].length; i++ )
	  {

	    total+=Groups[j][i];

	  } 

	  newCentroid=total/Groups[newGroup].length;  

	  Centroids[j]=newCentroid;

	}

    for( j=0; j < Clusters; j++ )
	{

	  if ( Centroids[j]!=oldCentroids[j] )
	  {

	    changed=true;

	  }

	}

  }
  while( changed==true );

  return Groups;

}

Download the script (right click and choose save target as)

I’ve expanded the script now to support multiple dimensions, you can see my script here.

Filed under: Mathematics,Programming — Tags: algorithm, javascript, k means, learning, mathematics, maths — admin @ 8:35 pm