Glenn Geenen

I just did some more research in the fast sorting algorithms. Seems you can increase the speed of a Quick Sort by using an Insertion Sort when you need to sort a really small collection (as in less than 20 objects). Many sources say you get the best performance by sorting collections smaller than 9 by using Insertion Sort, in actionscript I got the best results between 20 and 30.

So first we need an Insertion Sort:

private static function insertionSort(input:Array, left:int, right:int):void
{
	var i:int, j:int, tmp:int, orgLeft:int = left - 1;
	for (i = left + 1; i < right; i++)
	{
		tmp = input[i];
		j = i - 1;

		while (j >= 0 && tmp < input[j])
		{
			input[j + 1] = input[j];
			j--;
		}
		input[j + 1] = tmp;
	}
}

Now we can change our Quick Sort:

public static function quickSort2(arrayInput:Array, left:int, right:int):void
{
	var i:int = left, j:int = right, pivotPoint:int = arrayInput[Math.round((left + right) * .5)], tempStore:int;

	if (right - left < 25)
	{
		insertionSort(arrayInput, left, right);
	}
	else
	{
		while (i <= j)
		{
			while (arrayInput[i] < pivotPoint)
			{
				i++;
			}
			while (arrayInput[j] > pivotPoint)
			{
				j--;
			}
			if (i <= j)
			{
				tempStore = arrayInput[i];
				arrayInput[i] = arrayInput[j];
				i++;
				arrayInput[j] = tempStore;
				j--;
			}
		}
		if (left < j)
		{
			quickSort2(arrayInput, left, j);
		}
		if (i < right)
		{
			quickSort2(arrayInput, i, right);
		}
	}
}

Again from slow to fast sorting.

Merge Sort:

public static function mergesort(a:Array):Array
{
	if (a.length <= 1)
		return a;
	else
	{
		var middle:uint = a.length / 2;
		var left:Array = [middle], right:Array = [a.length - middle], j:uint = 0;

		for (var i:uint = 0; i < middle; i++)
			left[i] = a[i];
		for (i = middle; i < a.length; i++)
			right[j++] = a[i];

		left = mergesort(left);
		right = mergesort(right);

		if (left[left.length - 1] <= right[0])
			a = left.concat(right);
		else
			a = merge(left, right);
		return a;
	}
}

private static function merge(left:Array, right:Array):Array
{
	var result:Array = [left.length + right.length];
	var j:uint = 0, k:uint = 0, m:uint = 0;
	while (j < left.length && k < right.length)
	{
		if (left[j] <= right[k])
			result[m++] = left[j++];
		else
			result[m++] = right[k++];
	}
	for (; j < left.length; j++)
		result[m++] = left[j];
	for (; k < right.length; k++)
		result[m++] = right[k];
	return result;
}

Shell Sort:

public static function shellsort(invoer:Array, lengte:int):void
{
	var i:int, j:int, t:int, kol:int;
	for (kol = lengte / 3; ; kol /= 3)
	{
		if (kol == 0)
			kol = 1;
		for (i = kol; i < lengte; i++)
		{
			j = 0;
			while (i - j >= kol && invoer[i - j] < invoer[i - kol - j])
			{
				t = invoer[i - j];
				invoer[i - j] = invoer[i - kol - j];
				invoer[i - kol - j] = t;
				j += kol;
			}
		}
		if (kol == 1)
			return;
	}
}

Here we have the Comb Sort 11 variant, when gap ending on 11 it’s faster than on 10 or 9. Comb Sort:

public static function combSort11(input:Array):void
{
	var i:int, gap:int = input.length, length:uint = input.length, swapped:Boolean = false, tmp:int;
	while (gap > 1 || swapped)
	{
		if (gap > 1)
			gap /= 1.3;
		swapped = false;

		if (gap == 9 || gap == 10)
			gap = 11;

		for (i = 0; i + gap < length; i++)
		{
			if (input[i] > input[i + gap])
			{
				tmp = input[i];
				input[i] = input[i + gap];					input[i + gap] = tmp;
				swapped = true;
			}
		}
	}
}

Now we come to the fastest sorting I tried out (I’ll keep looking for sorting optimizations). Quick Sort is 100 times faster than Bubble Sort and 50 times faster than Minmax Sort. Quick Sort is twice as fast as Merge Sort.

Quick Sort:

public static function quickSort(arrayInput:Array, left:int, right:int):void
{
	var i:int = left, j:int = right, pivotPoint:int = arrayInput[Math.round((left + right) * .5)], tempStore:int;

	while (i <= j)
	{
		while (arrayInput[i] < pivotPoint)
		{
			i++;
		}
		while (arrayInput[j] > pivotPoint)
		{
			j--;
		}
		if (i <= j)
		{
			tempStore = arrayInput[i];
			arrayInput[i] = arrayInput[j];
			i++;
			arrayInput[j] = tempStore;
			j--;
		}
	}
	if (left < j)
	{
		quickSort(arrayInput, left, j);
	}
	if (i < right)
	{
		quickSort(arrayInput, i, right);
	}
}

For Windows you’ll need to install: http://code.google.com/p/msysgit/downloads/list

Now start terminal (mac) or git bash (windows).

First you’ll need to create a ssh key.

cd ~/.ssh

It’ll say “No such file or directory“.

ssh-keygen -t rsa -C "email@email.com"

Press enter and type a passphrase twice.

Now you’ll need to open the next file: /Users/username/.ssh/id_rsa.pub and copy the entire content (.ssh is a hidden folder). Go to the GitHub website and paste the key under Account Settings -> SSH Public Keys -> Add another public key.

Now you can check if everything works:

ssh -T git@github.com

Type yes and your passphrase when asked.

Now we register your info with git:

git config --global user.name "myname"
git config --global user.email "myemail"

Now when you want to get a repository from the web, you go to the folder you want to put the repository in.

git clone git@github.com:username/repositoryname.git

If you want to create a repository, follow this link: http://help.github.com/create-a-repo/

From now on you can use git from the moment you’re located in the folder containing the git repository.

Commands:

Get the status of your repository.
git status

Get a list of all branches.
git branch

Get a log of all commits.
git log

Get the latest version from the server. By default it’ll pull from the branch you’re working on.
git pull
git pull <repository> <branch>

Create a new branch.
git branch <branchname>

Switch to a different branch or an older version.
git checkout <branchname / filename>

Add files you want to version control.
git add <files>

Commit changes.
git commit -m “message here”

Put your changes on the server, your changes have to be committed to do this. By default it’ll push to the branch you’re working on.
git push
git push <repositoy> <branch>

See the changes between two different branches.
git diff <branchname1> <branchname2>

Merge the named branch into your current branch.
git merge <branchname>

I was looking into different sorting algorithms and decided to write them in Actionscript, since I was busy practising Actionscript. I’ll start with the basic sorting algorithms, these are the easiest to write but are the slowest algorithms.

The most basic of all sorting is the bubble sort. It just goes over the whole collection and puts the largest item at the back of the collection.

Bubble Sort:

public static function bubbleSort(invoer:Array):void
{
	var tmp:int, i:int, length:int = invoer.length, finished:Boolean, changed:Boolean;
	while (!finished)
	{
		changed = false;
		for (i = 0; i < length; ++i)
		{
			if (invoer[i - 1] > invoer[i])
			{
				tmp = invoer[i - 1];
				invoer[i - 1] = invoer[i];
				invoer[i] = tmp;
				changed = true;
			}
		}
		if (changed)
		{
			--length;
		}
		else
		{
			finished = true;
		}
	}
}

We can optimize the bubble sort by sorting both directions, not only getting the largest item to the end but also getting the smallest item to the front. This is what is called Cocktail Sort.

Cocktail Sort:

public static function cocktailsort(invoer:Array):void
{
	var swapped:Boolean = true, i:int, length:int = invoer.length, begin:int = -1, tmp:int;
	while (swapped)
	{
		swapped = false;
		for (i = 0; i < length; i++)
		{
			if (invoer[i] > invoer[i + 1])
			{
				tmp = invoer[i + 1];
				invoer[i + 1] = invoer[i];
				invoer[i] = tmp;
				swapped = true;
			}
		}

		if (swapped)
		{
			--length;
			swapped = false;
			for (i = length - 2; i > begin; i--)
			{
				if (invoer[i] > invoer[i + 1])
				{
					tmp = invoer[i + 1];
					invoer[i + 1] = invoer[i];
					invoer[i] = tmp;
					swapped = true;
				}
			}
			if (swapped)
				++begin;
		}
	}
}

Another approach is going over the list and finding the smallest item, we will swap the smallest item to the first place in the list. Then we’ll swap the second smallest item to the second position and so on, this is called selection sort.

Selection Sort:

public static function selectionSort(invoer:Array):void
{
	var length:int = invoer.length, begin:int = 0, index_of_min:int, temp:int, started:Boolean;
	while (begin < length)
	{
		index_of_min = begin;
		started = false;
		for (temp = begin; temp < length; temp++)
		{
			if (!started || invoer[index_of_min] > invoer[temp])
			{
				index_of_min = temp;
			}
			started = true;
		}

		temp = invoer[begin];
		invoer[begin] = invoer[index_of_min];
		invoer[index_of_min] = temp;

		++begin;
	}
}

Now we can optimize the selection sort by doing it in two directions, this is called minmax sort.

MinMax Sort:

public static function minmaxSort(invoer:Array):void
{
	var end:int = invoer.length - 1, begin:int = 0, index_of_min:int, index_of_max:int, temp:int, started:Boolean;

	while (begin < end)
	{
		started = false;
		for (temp = begin; temp <= end; temp++)
		{
			if (!started)
			{
				index_of_min = temp;
				index_of_max = temp;
				started = true;
			}
			else
			{
				if (invoer[temp] < invoer[index_of_min])
					index_of_min = temp;
				else if (invoer[temp] > invoer[index_of_max])
					index_of_max = temp;
			}
		}

		if (index_of_max == begin && index_of_min == end)
		{
			temp = invoer[index_of_max];
			invoer[index_of_max] = invoer[index_of_min];
			invoer[index_of_min] = temp;
		}
		else if (index_of_max == begin)
		{
			temp = invoer[index_of_max];
			invoer[index_of_max] = invoer[end];
			invoer[end] = temp;

			temp = invoer[begin];
			invoer[begin] = invoer[index_of_min];
			invoer[index_of_min] = temp;
		}
		else
		{
			temp = invoer[begin];
			invoer[begin] = invoer[index_of_min];
			invoer[index_of_min] = temp;

			temp = invoer[index_of_max];
			invoer[index_of_max] = invoer[end];
			invoer[end] = temp;
		}
				++begin;
				--end;
			}
			trace(invoer);
		}
	}
}

At this point the MinMax sort is the fastest one, it’s two times faster than the original bubble sort. But still these sort algorithms are really slow, so don’t be bothered using them. I’ll put some fast sorting algorithms in the next post.

Here I share some code of how to create a custom actionscript popup. The example below is a popup with an image in. When you click outside the popup it’ll close.

You create a popup like this:

import myPackage.ImagePopup;
import  mx.core.IFlexDisplayObject;
import mx.managers.PopUpManager;

var _imagePopup:ImagePopup = new ImagePopup("image.jpg");
PopUpManager.addPopUp(_imagePopup,this.parentApplication as DisplayObject, true);

Here is the ImagePopup class:

package myPackage
{
  import flash.events.Event;
  import mx.controls.Image;
  import mx.events.FlexMouseEvent;
  import mx.managers.PopUpManager;
  import mx.core.IFlexDisplayObject;
  import spark.components.TitleWindow;

  public class ImagePopup extends TitleWindow
  {
    private var _image:Image;  

    public function ImagePopup(src:String)
    {
      super();
      title = "Title Here";
      x=y=5;
      width=402;
      height=433;
      this.addEventListener(Event.CLOSE,closePopup);
      _image = new Image();
      _image.x = 0; _image.y = 0; _image.width = 400; _image.height = 400;
      _image.source = src;
      addElement(_image);
      this.addEventListener(FlexMouseEvent.MOUSE_DOWN_OUTSIDE, closePopup);
    }
    private function closePopup(e:Event):void
    {
      PopUpManager.removePopUp(this as IFlexDisplayObject);
    }
  }
}

Just an easy way to do collision detection. The way I did it here (really simple) is creating a main character image and a spark group with all the enemies in.

Example setup:

<mx:Image includeIn=”Game” x=”400″ y=”500″ source=”@Embed(”assets/hero.png”)” id=”_hero” width=”100″ height=”100″/>

<s:Group id=”enemies” includeIn=”Game”>
<mx:Image x=”500″ y=”-150″ source=”@Embed(”assets/image.png”)” width=”100″ height=”100″/><mx:Image x=”100″ y=”-500″ source=”@Embed(”assets/image.png”)” width=”100″ height=”100″/><mx:Image x=”400″ y=”0″ source=”@Embed(”assets/image.png”)” width=”100″ height=”100″/></s:Group>

private function onTick(event:TimerEvent):void
{
  var obj:DisplayObject;
  for(var i:int = 0; i < enemies.numChildren; ++i)
  {
    obj = enemies.getChildAt(i);
    obj.y += 5;
    if(obj.y > 600) obj.y = -150;
    if(componentsCollide(obj)) endGame();
  }
}
private function componentsCollide(obj:DisplayObject):Boolean
{
  var bounds1:Rectangle = new Rectangle(obj.x,obj.y,obj.width,obj.height);
  var bounds2:Rectangle = new Rectangle( _hero.x,_hero.y, _hero.width, _main.hero);
  return bounds1.intersects( bounds2 );
}

Some tips I found out on getting better performance in Flex.

1. Use a background image that is a SWF or SVG file. These are easier for Flash Player to redraw. Use PNG above JPG or GIF.
2. The setStyle() method is one of the most expensive calls in the Flex application model framework.
3. Hard coding positions, heights and widths give you better performance.
4. Multiple Flex applications can load Runtime Shared Libraries at runtime, but each client needs to download them only once.
5. Data Binding takes up memory and can slow down the application start-up. It may be more efficient to do an assignment in code rather than using binding.
6. Local variable access is faster, so assign variables to local if they are accessed a lot. They will be stored on the stack and access is much quicker.
7. Whenever you have a set function, only assign the new value if they”re not equal to each other.
8. Spark Groups are lighter than mx Containers.
9. Reduce number of nested groups.
10. Spark BitmapImage is lighter than mx Image. mx Image is lighter than Spark Image.
11. Use Label over RichText.

Tip: Test your application on an old computer.