# Quick Tip: Implementing the Bubble Sort in AS3

##### Tutorial Details
• Difficulty: Beginner
• Platform: Flash (Flash Player 9+)
• Language: AS3
• Software used: Flash Professional CS3
• Estimated Completion Time: 20 minutes

In this Quick Tip, I’ll show you how and why the Bubble Sort algorithm works, and how to implement it in AS3. You’ll end up with a class that you can use in any Flash project, for sorting any array.

## Final Result Preview

Here’s a simple demo of the result of the bubble sort algorithm:

Of course, this SWF doesn’t prove much on its own! Grab the source files and you can edit the input array yourself.

## Step 1: Creating the BubbleSort Class

As this algorithm will be used more than once, it’s a good idea to create a class for it, so that we can easily use it in any AS3 project:

Set up a basic Flash project, and inside the project folder create a file BubbleSort.as. (We will create a tester file here too, so we can test it.)

If you dont know how to work with classes please check this tutorial: How to Use a Document Class in Flash.

We wont need the constructor, so get rid of it! Your class should look like this:

package
{

public class BubbleSort
{

}

}

## Step 2: How the Algorithm Works

This algorithm is not the fastest or most efficient method of sorting a series of numbers, but it is the easiest one to understand.

This image sums it up; at every stage, each pair of numbers are compared, starting from the end, and swapped (by means of a “spare” temp variable) if they are in the wrong order.

Once all consecutive pairs have been checked, this guarantees that the number at the start is the largest number in the sequence; we then repeat, checking every pair of numbers apart from the number at the start. Once all consecutive pairs have been checked, we know that the first two numbers in the sequence are in the correct order (they are the largest and second-largest). We keep going until we’ve put every number in the correct order.

It’s called the “bubble sort” because, on each pass through the array, the biggest number “floats” to the top of the array, like a bubble in water.

Lets start writing the code. We’ll call the main function bsort():

package
{

public class BubbleSort
{
public function bsort(arr:Array,sortType:String):Array
{
var temp:String;
if(sortType.toLocaleLowerCase() == "descending")
{

}
else if(sortType.toLocaleLowerCase() == "ascending")
{

}
else
throw new Error("You have a typo when Calling the bsort() function, please use 'ascending' or 'descending' for sortType!");

return arr;
}

}

}

The function gets two parameters. The first parameter, arr, will be the array to be sorted; the second paramter, sortType will be used to decide if the user wants the array to be sorted in ascending or descending order.

In the function we declare a temp variable which will hold the elements of the array in case we need to swap the two elements. You may wonder why it is not a Number. It’s because our class will be able to handle String arrays too, sorting them alphabetically; we can convert numbers to strings and back again, but we can’t convert strings to numbers and back again, so we use a String for this variable, just to be safe.

We use an if-else block to split our code into two branches, depending on which direction the user wants to sort in. (If the user does not provide a valid choice, the program will fire an error.)

The difference between the code in either branch will be just one character: either < or >.

package
{

public class BubbleSort
{
public function bsort(arr:Array,sortType:String):Array
{
var temp:String;
if(sortType.toLocaleLowerCase() == "descending")
{
for(var i:uint=0; i < arr.length; i++)
{
for(var j:uint=arr.length-1; j > i; j--)
{

}
}
}
else if(sortType.toLocaleLowerCase() == "ascending")
{

}
else
throw new Error("You have a typo when Calling the bsort() function, please use 'ascending' or 'descending' for sortType!");

return arr;
}

}

}

As you can see, we’re using nested for loops. One goes from the first element to the last element of the array; the other goes backwards.

Let’s inspect the inner “j” loop first. As the earlier diagram shows, we begin by comparing the last two elements of the array, which are arr[j-1] and arr[j] (in the first iteration). If arr[j-1] is less than arr[j] they need to be swapped.

In either case we subtract one from j (through the “j--” call in line 131), which changes which pair of numbers will be compared on the next loop.

j starts at a value of arr.length-1, and ends with a value of 1, meaning that the inner for loop checks every consecutive pair, starting with the last pair (where j equals arr.length-1) and ending with the first pair (where j equals 1).

Now let’s look at the outer “i” loop. Once all the pairs have been checked and swapped as necessary, i is increased (through the “i++” call in line 129). This means that, the next time round, j will start at arr.length-1 again, but end at 2 this time – meaning that the first pair in the sequence will not be checked or swapped. This is exactly what we want, since we know that the first number is in the correct position.

As it goes on, eventually there will be only two elements that need to be checked in the inner loop. Once they’re done, we know we’ve sorted the array!

Here’s what that looks like in code:

				for(var i:uint=0; i<arr.length;i++)
{
for(var j:uint=arr.length-1; j > i; j--)
{
if (arr[j-1] < arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}

Now we can use the same logic to create the ascending sort:

We need only to change the comparison operator in the if block of the inner loop:

package
{

public class BubbleSort
{

public function bsort(arr:Array,sortType:String):Array
{
var temp:String;
if(sortType.toLocaleLowerCase() == "descending")
{
for(var i:uint=0; i<arr.length;i++)
{
for(var j:uint=arr.length-1; j > i; j--)
{
if (arr[j-1] < arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
else if(sortType.toLocaleLowerCase() == "ascending")
{
for(var k:uint=0; k<arr.length;k++)
{
for(var l:uint=arr.length-1; l > k; l--)
{
if (arr[l-1] > arr[l])
{
temp = arr[l-1];
arr[l-1] = arr[l];
arr[l] = temp;
}
}
}
}
else
{
throw new Error("You have a typo when Calling the bsort() function, please use 'ascending' or 'descending' for sortType!");
}

return arr;
}
}

}

## Step 3: Creating the Tester Application

Create a new flash file, tester.fla, in the same folder as BubbleSort.as. Create two dynamic text fields, name one input_arr and the other one output_arr.

After creating the appearance, we must create and link the document class.

Create a file Tester.as and link this to tester.fla

Now we can finally use our class in the Tester.as:

package
{
import BubbleSort;
import flash.display.MovieClip;

public class Tester extends MovieClip {

private var bs:BubbleSort = new BubbleSort();

public function Tester() {
var ar:Array = [5,7,9,8,1,3,6,2,4,5,0];
input_arr.text = ar.toString();
ar = bs.bsort(ar,"descending");
output_arr.text = ar.toString();
}
}
}


In this line, we call the bsort() function of our variable bs (which is an instance of BubbleSort):

ar = bs.bsort(ar,"ascending");

This function returns an array, so we can assign this as the new value of our original input array.

Save everything and try your work out.

## Conclusion

In this tutorial we created a function to help us sort an Array. We could improve the efficiency; for more on that, you can read Wikipedia – Bubble Sort

If you really wish to see how fast this algorithm is compared to the other options (like quicksort), take a look at sorting-algorithms.com.

Fuszenecker Zsombor is zsbee on Activeden
• Vishwas

What is the advantage of using our own method ( Selection, Bubble Sort etc) as compared to “sort” function already available in AS3 ?

• Fuszenecker Zsombor

To be honest, there is no real advantage of using your own. This tutorial is rather for the explination there, so you can understand how these sorting algorithms work in real life. :)

• Shafeen

There is no advantage, at all……I think this was more of a conceptual post.

• Rokas

I am not really a AS3 programmer but as far as i had to read, if you are going to use only bubble or only selection sorting algorithms, you cannot beat internal sorting algorithm on speed because it works at lower level. But some of the studies showed that quicksort + insertion combination can work at faster speed than the internal sorting, I also believe that that was proven even mathematically that the combination of quicksort/insertion is fastest sorting algorithm when working with large sets of data. But things might have changed since i read about it probably like couple years back :)

• David

I can totally believe the idea that a quicksort will have better performance over the provided sort function specially on large sets of data. It would be fun to test it but I don’t have the time.

• Fuszenecker Zsombor

Yes, it is faster. There is a link at the end of the Quick Tip too :) (sorting-algorithms.com – press the green “recycle” button)