AS3 gives you arrays and a way to sort them, but no easy way to keep them sorted as you add elements to them. Today’s article discusses an easy way to do just that: build a sorted array and keep it sorted. As a bonus, the array provides very fast searching for the elements it contains.

When you have a sorted array you can use a binary search to quickly find elements in the array. A binary search will run in, at the worst case, log(N) operations, where N is the size of the array. With an unsorted array, the search will take N operations. Here’s a comparison:

Size Unsorted Search Operations Sorted Search Operations
10 10 3
100 100 7
1000 1000 10
10000 10000 13
100000 100000 17
1000000 1000000 20

The difference between them is huge even at small sizes like 100 and only grows from there. With that in mind, you’ll understand the indexOf function of the SortedArray class here:

package
{
	public class SortedArray
	{
		public var array:Array = [];
 
		public function add(element:*): int
		{
			var leftIndex:int;
			var rightIndex:int = array.length-1;
			var middleIndex:int;
			var middleElement:*;
 
			while (leftIndex <= rightIndex)
			{
				middleIndex =  (rightIndex+leftIndex) / 2;
				middleElement = array[middleIndex];
				if (middleElement < element)
				{
					leftIndex = middleIndex + 1;
				}
				else if (middleElement > element)
				{
					rightIndex = middleIndex - 1;
				}
				else
				{
					array.splice(middleIndex, 0, element);
					return middleIndex;
				}
			}
			array.splice(leftIndex, 0, element);
			return leftIndex;
		}
 
		public function indexOf(element:*): int
		{
			var leftIndex:int;
			var rightIndex:int = array.length-1;
			var middleIndex:int;
			var middleElement:*;
 
			while (leftIndex <= rightIndex)
			{
				middleIndex =  (rightIndex+leftIndex) / 2;
				middleElement = array[middleIndex];
				if (middleElement < element)
				{
					leftIndex = middleIndex + 1;
				}
				else if (middleElement > element)
				{
					rightIndex = middleIndex - 1;
				}
				else
				{
					return middleIndex;
				}
			}
			return -1;
		}
	}
}

But what about the add function? Well, you may have noticed that it looks awfully similar to the indexOf function. That’s because it is the same exact binary search algorithm as in indexOf, but tweaked to insert instead of getting an index. You see, one handy side-effect of the binary search algorithm is that it narrows in on the index of the element being searched for. When we find the element, it’s simple to add a duplicate element right where it is. When we don’t find it, we know where it should have been and simply add it there.

So, how do you use the SortedArray class instead of a regular Array? For the most part you simply use its array field like you always have used an Array: loop over it, remove elements from it, etc. Just make sure you don’t add elements to it directly via a function like push or unshift. Also, don’t change its elements via the index [] operator. If you do either of these, the array will no longer be sorted and both the indexOf and add functions will break.

I could have designed the class to keep the array private and be a lot safer to use, but I intentionally chose not to for the sake of performance. If the array was private, it’d be much more expensive to iterate over it or call any of its functions. It should be pretty easy to make the array private and wrap its API If you’d like a safer version of the class.

Now, let’s put theory to the test and see how SortedArray stacks up against a regular Array when it comes to the two features of the class: adding and searching for elements.

package
{
	import flash.display.Sprite;
	import flash.display.StageAlign;
	import flash.display.StageScaleMode;
	import flash.text.TextField;
	import flash.text.TextFieldAutoSize;
	import flash.utils.getTimer;
 
	public class SortedArrayTest extends Sprite
	{
		private var logger:TextField = new TextField();
		private function row(...cols): void { logger.appendText(cols.join(",")+"\n"); }
 
		public function SortedArrayTest()
		{
			stage.align = StageAlign.TOP_LEFT;
			stage.scaleMode = StageScaleMode.NO_SCALE;
 
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
 
			var beforeTime:int;
			var afterTime:int;
			var unsortedAddTime:int;
			var sortedAddTime:int;
			var unsortedIndexOfTime:int;
			var sortedIndexOfTime:int;
			var i:int;
			var REPS:int = 1000;
			var SIZES:Array = [10,100,1000,10000];
 
			row(
				"Size",
				"Unsorted Add Time",
				"Sorted Add Time",
				"Unsorted IndexOf Time",
				"Sorted IndexOf Time"
			);
 
			for each (var size:int in SIZES)
			{
				var values:Array = [];
				for (i = 0; i < size; ++i)
				{
					values.push(i);
				}
				values.sort(function(a:int, b:int):int { return Math.random()<0.5?-1:1; });
 
				var unsortedArray:Array = [];
				beforeTime = getTimer();
				for (i = 0; i < size; ++i)
				{
					unsortedArray.push(values[i]);
				}
				afterTime = getTimer();
				unsortedAddTime = (afterTime-beforeTime);
 
				var sortedArray:SortedArray = new SortedArray();
				beforeTime = getTimer();
				for (i = 0; i < size; ++i)
				{
					sortedArray.add(values[i]);
				}
				afterTime = getTimer();
				sortedAddTime = (afterTime-beforeTime);
 
				beforeTime = getTimer();
				for (i = 0; i < size; ++i)
				{
					unsortedArray.indexOf(values[i]);
				}
				afterTime = getTimer();
				unsortedIndexOfTime = (afterTime-beforeTime);
 
				beforeTime = getTimer();
				for (i = 0; i < size; ++i)
				{
					sortedArray.indexOf(values[i]);
				}
				afterTime = getTimer();
				sortedIndexOfTime = (afterTime-beforeTime);
 
				row(
					size,
					unsortedAddTime,
					sortedAddTime,
					unsortedIndexOfTime,
					sortedIndexOfTime
				);
			}
		}
	}
}

I ran this performance test in the following environment:

  • Flex SDK (MXMLC) 4.6.0.23201, compiling in release mode (no debugging or verbose stack traces)
  • Release version of Flash Player 11.2.202.235
  • 2.4 Ghz Intel Core i5
  • Mac OS X 10.7.3

And here are the results I got:

Size Unsorted Add Time Sorted Add Time Unsorted IndexOf Time Sorted IndexOf Time
10 0 0 0 0
100 0 0 1 0
1000 0 3 4 1
10000 1 64 482 3

Performance Chart (all iterations)

Performance Chart (small iterations)

These results make it clear that the theory is working out in reality. You can see the unsorted search time grow linearly but the sorted search time grow much slower- logarithmically. Even at only 1000 elements in the array, the sorted version is four times faster than the unsorted version. At 10,000 elements, the gap widens to 160x.

As for the time to add elements to the arrays, the unsorted version is clearly quicker since it does not attempt to find the correct index to insert at in order to maintain a sorted array. So when choosing an approach with your own code, you’ll need to balance this extra time to insert against a purely unsorted approach or an approach where you add a lot of elements unsorted and then sort the array. Since the array is a public field of SortedArray, it’s easy to do this:

var sa:SortedArray = new SortedArray();
for (var i:int; i < 10000; ++i)
{
    sa.array.push(int(Math.random()));
}
sa.array.sort(Array.NUMERIC);

I hope you find the above class useful the next time your programming task calls for a sorted array. If you’ve spotted a bug or have a suggestion, please feel free to comment!